Discrete Mathematics for Computer Science

Comparing Growth Rates of Functions 295

Now, show that n 0 O(ln(n)). Working toward a contradiction, suppose n E O(ln(n)).

That is, for some integer No and some real number c, n < c l In(n) for all n > No. Then,

however, for any integer n such that n > max {No, 11,

2n < e n (fact (a))

en <_ ec(ln(n)) = n • ec (fact (b) and assumption of proof)

2' < n • ec

This implies that 2' E O(n), contradicting Theorem 7. 0

Complexity Comparisons for Various Functions

To see the difference in the time requirement for processing data sets of arbitrary size, we

will assume a single machine cycle will require 10-6 seconds to be completed. Table 5.1

gives the time required to process a data set of size n, for six different values of n, if it

takes log2(n) (n, n^2 , n^5 , and 2n, respectively) machine cycles to make the computation.

For example, in the column labeled n^2 for the row labeled n = 100, 1002 operations are

needed to complete execution. The time is (102)210-6 seconds = 10-2 seconds.

Table 5.1 Complexity Table for Several Functions

F(n) 10g2(n) n n2 n^5 r

n = 10 3 x 10-6 sec 10-5 sec 10-4 sec 0.1 sec 10-3 sec

n=20 4x 10-6 sec 2x 10-^5 sec 4x 10-4 sec 3sec Isec

n = 50 6 x 10-6 sec 5 x 10-5 sec 3 x 10-3 sec 5 min 36 yrs

n = 100 7 x 10-6 sec 10-4 sec 10-2 sec 3 hrs 4 x 1016 yrs

n = (^1000 1) x 10-5 sec 10-3 sec 1 sec 32 yrs 3.9 x 10287 yrs
n = 100, 000 2 x 10-5 sec 0.1 sec 2.7 hrs 3 x 1011 yrs > 1030,089 yrs
To better appreciate the figures in the last column, note that the current conjectured
age of the universe is around 2 x 1010 years. Now, suppose we could speed up the com-
putation by a factor of 1010 (which is not conceivable at the time of this writing). Also,
suppose we could somehow replace every elementary particle in the universe with one of
those computers (a physical impossibility, of course)-less than 1090 computers by current
estimates-and somehow simply split the computation equally among all those computers
(and such a simple, optimal split also is not currently conceivable). That reduces the largest

running time to over 1029,989 years-or over 1029,979 times the current age of the universe.

(Computer users do not like to wait that long for answers.)

The discussion in this section has shown that a function F is more complex than a

function G when G E O(F) but F 0 O(G). To show how important this idea is in com-

puter science, we used some relatively familiar functions for a table to show how they
differed when acting on inputs of various sizes. It is instructive to see how important the
function that describes the complexity of a computation really is by comparing various
entries in Table 5.1.