6.1 Asymptotic Growth Rate 285
In the following, we
any k > - 1, recall that
Define log* n = min{k
study a function that grows very slowly to infinity. For
lg^0 (k) n= lg^0 l Y l logn. ’
k1 k > - l,log(k) n < - 1).
Example 6.5 Show that log* n + log@) n for any constant integer m > - 1.
Proof. We first prove that for any fixed m > 2 and sufficiently large n,
log* n < logcn) n. To do so, we note that 2” > - zn for n - > 4. It follows that
n>4=> - 2$logn<n. -Repeatedly applying this inequality, we obtain
log+‘) n > - 4 =3 2i + log@) n < - n.
Now, for log n > 4m, substituting log n - 2m for i and log@) n for n, we
get
2(log n - 2m) < - 2(log n - 2m) + log(log* n-m) n < - logcm) n.
(Note*. log@) (log(‘) n) = log@+“) n 9 and so
logCi-l) log(“) n = log(‘Og* n-m-1) n > - 2” > - 4.)
That is, if n is so large such that log* n > 4m, then
log n < - 2 log n - 4m < - logcm) n.
Now, we note that for any fixed m > - 1, log(“+‘) n 4 log(m) n (see Exercise
6). Together, we get log* n 3 log(m) n.^0
Exercise 6.1
- Show that 21nn = o(n) and 210g(2n) = O(n).
- Show that (logn)‘” 4 do + 2Q”gn)‘“.
- Compare the following three functions using the + notation:
log n
2” 7 n(lOE? n)2 7 (log n>2”.
- Compare 2 log* n with n using the^4 notation.