6.1 Asymptotic Growth Rate 283
time f( 10) = 1023 is definitely acceptable; however, when the input size grows
to n = 64, it becomes unmanageable. The reason why this happens is that the
solution time f(n) = 2” - 1 grows too fast: its value doubles when the input
value increases by only one. This suggests that we measure the computational
complexity of an algorithm by the growth rate of its running time. If the run-
ning time of the fastest algorithm for a problem grows at such a fast rate,
then this algorithm (and, hence, this problem) is considered infeasible. In the
following, we present the general notations and techniques for measuring and
comparing the growth rates of different functions.
A function f( n ) is said to grout slower than a function g(n) (or, g(n) grows
faster than f(n)), denoted by f(n) 4 g(n), if
lm i f( >
n0
n+mgo= lFor example, g(n) = n2 grows faster than f(n) = n since
1
lim $ = lim - = 0.
n+cm n n+oo nThe relation 4 is a partial ordering:
Proposition 6.2 If f(n) 4 g(n) and g(n) + h(n), then f(n) 4 h(n).
PT-oaf By definition, if f(n) -+ g(n) and g(n) 3 h(n), then
lim -!- f( > - lim -!- 9( > = 0.
n--m g(n) - n-+m h(n)Therefore,
Iim f(^1
n
n>mh(n)=lim f(n) .-- g(n)
n-+m g(n) h(n) -0
’This means that f(n) + h(n). Cl
Two other commonly used notations are big-0 and small-o: We write
f( ) = o(g(n)) if f(n)^4 g(n), and f(n) = O(g(n)) if for some constant
Land for almost all n > 0, f(n) 5 Kg(n).’
The following sequences of functions appear very often in the study of
computational complexity:
Poly-log Sequence: {(logn)i 1 i = 1,2, l. •}.~
Polynomial Sequence: {d 1 i = 1,2, + l 0).
Subexponential Sequence: {nQ”gn)’ 1 i = 1,2, l -0).’ “For almost all .n^2 0” means “for all but fi nitely many n^2 0.”
2 For simplicity, we denote log = log2 for the rest of this chapter.