Example 3.1. Let f (x) := x2 and g(x) := 2x2 ’ x + 1. Then f = O(g) and

f = „¦(g). Indeed, f = ˜(g). 2

Example 3.2. Let f (x) := x2 and g(x) := x2 ’ 2x + 1. Then f ∼ g. 2

33

34 Computing with large integers

Example 3.3. Let f (x) := 1000x2 and g(x) := x3 . Then f = o(g). 2

Let us call a function in x eventually positive if it takes positive values

for all su¬ciently large x. Note that by de¬nition, if we write f = „¦(g),

f = ˜(g), or f ∼ g, it must be the case that f (in addition to g) is eventually

positive; however, if we write f = O(g) or f = o(g), then f need not be

eventually positive.

When one writes “f = O(g),” one should interpret “· = O(·)” as a binary

relation between f with g. Analogously for “f = „¦(g),” “f = ˜(g),” and

“f = o(g).”

One may also write “O(g)” in an expression to denote an anonymous

function f such that f = O(g). As an example, one could write n i = i=1

n2 /2 + O(n). Analogously, „¦(g), ˜(g), and o(g) may denote anonymous

functions. The expression O(1) denotes a function bounded in absolute

value by a constant, while the expression o(1) denotes a function that tends

to zero in the limit.

As an even further use (abuse?) of the notation, one may use the big-O,

-Omega, and -Theta notation for functions on an arbitrary domain, in which

case the relevant bound should hold throughout the entire domain.

Exercise 3.1. Show that

(a) f = o(g) implies f = O(g) and g = O(f );

(b) f = O(g) and g = O(h) implies f = O(h);

(c) f = O(g) and g = o(h) implies f = o(h);

(d) f = o(g) and g = O(h) implies f = o(h).

Exercise 3.2. Let f and g be eventually positive functions in x. Show that

(a) f ∼ g if and only if f = (1 + o(1))g;

(b) f ∼ g implies f = ˜(g);

(c) f = ˜(g) if and only if f = O(g) and f = „¦(g);

(d) f = „¦(g) if and only if g = O(f ).

Exercise 3.3. Let f and g be eventually positive functions in x, and suppose

f /g tends to a limit L (possibly L = ∞) as x ’ ∞. Show that

(a) if L = 0, then f = o(g);

(b) if 0 < L < ∞, then f = ˜(g);

(c) if L = ∞, then g = o(f ).

Exercise 3.4. Order the following functions in x so that for each adjacent

3.1 Asymptotic notation 35

pair f, g in the ordering, we have f = O(g), and indicate if f = o(g), f ∼ g,

or g = O(f ):

√

x3 , ex x2 , 1/x, x2 (x + 100) + 1/x, x + x, log2 x, log3 x, 2x2 , x,

√

e’x , 2x2 ’ 10x + 4, ex+ , 2x , 3x , x’2 , x2 (log x)1000 .

x

Exercise 3.5. Suppose that x takes non-negative integer values, and that

g(x) > 0 for all x ≥ x0 for some x0 . Show that f = O(g) if and only if

|f (x)| ¤ cg(x) for some positive constant c and all x ≥ x0 .

Exercise 3.6. Give an example of two non-decreasing functions f and g,

both mapping positive integers to positive integers, such that f = O(g) and

g = O(f ).

Exercise 3.7. Show that

(a) the relation “∼” is an equivalence relation on the set of eventually

positive functions;

(b) for eventually positive functions f1 , f2 , g2 , g2 , if f1 ∼ f2 and g1 ∼ g2 ,

then f1 g1 ∼ f2 g2 , where “ ” denotes addition, multiplication, or

division;

(c) for eventually positive functions f1 , f2 , and any function g that tends

to in¬nity as x ’ ∞, if f1 ∼ f2 , then f1 —¦ g ∼ f2 —¦ g, where “—¦”

denotes function composition.

Exercise 3.8. Show that all of the claims in the previous exercise also hold

when the relation “∼” is replaced with the relation “· = ˜(·).”

Exercise 3.9. Let f1 , f2 be eventually positive functions. Show that if

f1 ∼ f2 , then log(f1 ) = log(f2 ) + o(1), and in particular, if log(f1 ) = „¦(1),

then log(f1 ) ∼ log(f2 ).

Exercise 3.10. Suppose that f and g are functions de¬ned on the integers

k, k + 1, . . ., and that g is eventually positive. For n ≥ k, de¬ne F (n) :=

n n

i=k f (i) and G(n) := i=k g(i). Show that if f = O(g) and G is eventually

positive, then F = O(G).

Exercise 3.11. Suppose that f and g are functions de¬ned on the integers

k, k +1, . . ., both of which are eventually positive. For n ≥ k, de¬ne F (n) :=

n n

i=k g(i). Show that if f ∼ g and G(n) ’ ∞ as

i=k f (i) and G(n) :=

n ’ ∞, then F ∼ G.

The following two exercises are continuous variants of the previous two

exercises. To avoid unnecessary distractions, we shall only consider functions

36 Computing with large integers

that are quite “well behaved.” In particular, we restrict ourselves to piece-

wise continuous functions (see §A3).

Exercise 3.12. Suppose that f and g are piece-wise continuous on [a, ∞),

x

and that g is eventually positive. For x ≥ a, de¬ne F (x) := a f (t)dt and

x

G(x) := a g(t)dt. Show that if f = O(g) and G is eventually positive, then

F = O(G).

Exercise 3.13. Suppose that f and g are piece-wise continuous [a, ∞), both

x

of which are eventually positive. For x ≥ a, de¬ne F (x) := a f (t)dt and

x

G(x) := a g(t)dt. Show that if f ∼ g and G(x) ’ ∞ as x ’ ∞, then

F ∼ G.

3.2 Machine models and complexity theory

When presenting an algorithm, we shall always use a high-level, and some-

what informal, notation. However, all of our high-level descriptions can be

routinely translated into the machine-language of an actual computer. So

that our theorems on the running times of algorithms have a precise mathe-

matical meaning, we formally de¬ne an “idealized” computer: the random

access machine or RAM.

A RAM consists of an unbounded sequence of memory cells

m[0], m[1], m[2], . . .

each of which can store an arbitrary integer, together with a program. A

program consists of a ¬nite sequence of instructions I0 , I1 , . . ., where each

instruction is of one of the following types:

arithmetic This type of instruction is of the form ± ← β γ, where rep-

resents one of the operations addition, subtraction, multiplication,

or integer division (i.e., ·/· ). The values β and γ are of the form c,

m[a], or m[m[a]], and ± is of the form m[a] or m[m[a]], where c is an

integer constant and a is a non-negative integer constant. Execution

of this type of instruction causes the value β γ to be evaluated and

then stored in ±.

branching This type of instruction is of the form IF β 3 γ GOTO i, where

i is the index of an instruction, and where 3 is one of the comparison

operations =, =, <, >, ¤, ≥, and β and γ are as above. Execution of

this type of instruction causes the “¬‚ow of control” to pass condi-

tionally to instruction Ii .

halt The HALT instruction halts the execution of the program.

3.2 Machine models and complexity theory 37

A RAM executes by executing instruction I0 , and continues to execute

instructions, following branching instructions as appropriate, until a HALT

instruction is executed.

We do not specify input or output instructions, and instead assume that

the input and output are to be found in memory at some prescribed location,

in some standardized format.

To determine the running time of a program on a given input, we charge

1 unit of time to each instruction executed.