Problem Solving in Automata, Languages, and Complexity

284 COMPUTATIONAL COMPLEXITY

Exponential Sequence: { 2in 1 i = 1,2, l l 0).

Superexponential Sequence: (an* 1 i = 1,2, l l l }.

It is easy to check that these sequences satisfy the following properties. We

leave the formal proof as an exercise to the reader.

(a) In each sequence, if i < j, then the ith function grows slower than the

jth function. For instance, n(l”gn)” 3 n(10gn)4.

(b) For any two sequences, every function in the former sequence grows

slower than any function in the latter sequence (except for the first

function of the last sequence). For instance, (log n)64 + ,l” 4 n(l”gnj4 4

23n -( 2n2.

It is interesting to note that these five sequences do not contain all possible

measurement for growth rates. The following are some examples not in these

sequences.

Example 6.3 Show that the function 2dl”gn grows slower than every func-

tion in the polynomial sequence, but faster than every function in the poly-log
sequence.

Proof. Using L’Hopital’s rule: we check that, for anv i > 1,

lirn (log n>i - lim

n-boo ~JJ/L& - n-boo

I Y - J

i(log n)i-l(log e)/n

- - lim

n-+oo

- - lim

n+oo

2dl”gn/(2nJiogn)

(2 loge) i (log n)i-1/2

22/logn

(210ge)2i i(; - l/2)@ - 1) l.. (l/2)

2&G

= 0

.

Therefore, (log n)i + 2dl”gn for any i > - 1. Also,

22/logn

lim p - - lim 2$G-l”gn = lim 24GG(1-l/iogn) - -^0.

n-m0 n n-boo n--boo

Therefore, 2@Ogn 4 n.^0

Example 6.4 Suppose f(n) + g(n). Sh ow that there exists a function h(n)
such that f(n) 4 h(n) -+ g(n).

Proof. Choose h(n) = J-f&J$$ Then,

lim f(^1

n

nLooh(n)=

=O, and lim n= h(^1 lim

n+00 h-4 n-boo