Discrete Mathematics for Computer Science

Comparing Growth Rates of Functions 285

2. Sometimes, two different computers execute various instructions at different relative
   speeds. C 1 may be twice as fast as C 2 at doing floating point operations, and C 2 may
   be twice as fast as C 1 at doing logical operations. The measure ignores constant factors,
   however, such as the two times factors.

We are interested in timing functions that input the size of the input data and output

the amount of time taken by the program. The input to such a function is a natural number,

and the output is a non-negative real number. Keep this idea in mind as we explore the next

notion.

Definition 1. Let F, G : [ 0, co) be functions. F asymptotically dominates G if,
for some integer No e N and some real number c E (0, oo) such that for all n > No,

G(n) < c. F(n)

The condition "for all n > No" in Definition 1 reflects the fact that finitely many inte-

gers can be ignored, since we are looking for a starting place for all following integers to

be instances where the condition holds: We do not worry about whether the inequality may

fail for some elements of the finite set {0, 1, 2 ... , No - 11. The multiplicative constant c

in Definition 1 reflects the fact that integer multiples of a function are considered to be the

"same" in complexity.

Example 1. Let F, G : N --+ [0, oo) be functions defined as G(n) = 3n and F(n) = n^2.

F asymptotically dominates G.

Solution. Let No = 0 and c = 3. It follows that for n > No,

G(n) = 3n

< 3n

2

< 3F(n)

< cF(n) U

Some authors allow F and G to take on negative values. Typically, the convention is

to study IF(n) I and IG(n) I in those cases.
It remains for us to develop the notion of asymptotic domination so that we can show
how a function represents the complexity of an algorithm. This notion is captured in the
"big 0" notation.

Definition 2. Let F, G : N -- [0, oo) be functions. Then,

O(F) = {G : F asymptotically dominates GI

The expression "F asymptotically dominates G" is usually not written out in full. It is

far more common to write "G E O(F)." The expression "O(F)" is pronounced "big-Oh of

F," or order of F. (With abuse of notation, people sometimes write "G is O(F)," or even

"= O(F)*" However, "O(G) = F" is never considered to be acceptable.)

If G E O(F) and F E O(G), the intuition is that F and G grow at approximately the

same rate. To understand this notion, we present some examples. Although the definition
is in terms of functions from N into [ 0, oo), we actually graph the functions on the usual
coordinate system for the (x, y)-plane.