Design and Analysis of Algorithms

Effi ciency of Algorithms 395

Example: log n ≤ O(n

1/2

)

n

1/2

is another way of writing the square root of n. From calculus, the derivative of this function is

1/(2n

1/2

). This derivative will overtake the derivative of log n, which is c /n. Equality occurs at the point

where

c /n = 1/(2n

1/2

)

that is, n = ⎡(4c

2

)⎤.

14.5.14 Order-of-Magnitude Comparisons

We give below a table of some common functions and their approximate values as n ranges over six orders

of magnitude.

Such tables give hints to the growth rate of functions, but cannot be considered a proof. For such proofs

we rely on analytic methods. In any case, such tables are instructive. For example, ...