Problems 3-6

	f(n)	c
a	n-1	0	n
b	lg n	1	lg* n
c	n/2	1	lg n
d	n/2	2	lg n – 1
e		2	lg lg n
f		1	∞
g		2
g	n/lg n	2	lg* n

Problems 3-5

Solution Wanted!

Problems 3-4

a. No, 1 = O(n), but n is not O(1).

b. No, 1 + n ≠ Θ(min(1,n)) = Θ(1).

c. Yes, f(n) ≤ cg(n), so lg f(n) = lg( g(n) ) + lg c.

d. No, 2n = O(n), but ≠ .

e. Only true for f(n) > 1

f. Yes, f(n)≤cg(n), so g(n) ≥ f(n)/c.

g. No, ≠ .

h. Yes

Problems 3-3

a.

Exponential: > > (n+1)! > n! > > > > .

Moderated Exponential: > .

Polynomial: > = > n lg n = lg n! > n = >

Polylogarithmic: > > ln n > > ln ln n.

Very slow: > lg *n = lg*(lg n) > lg (lg *n) > = 1.

b.

f(n) = 0, if n is odd. f(n) = , if n is even.

Problems 3-2

	A	B	O	o	Ω	ω	Θ
a.			Yes	Yes	No	No	No
b.			Yes	Yes	No	No	No
c.			No	No	No	No	No
d.			No	No	Yes	Yes	No
e.			Yes	No	Yes	No	Yes
f.	lg(n!)		Yes	Yes	Yes	No	Yes

Problems 3-1

a. If k ≥ d, then we choose c as , then there must exist some , such that p(n) ≤ for all n ≥ .

b.  If k ≤ d, then we choose c as , then there must exist some , such that p(n) ≥ for all n ≥ .

c. If k = d, then a and b’s condition holds. Hence p(n) = .

d. If k > d, then = 0, when n → ∞. Hence p(n) = .

e. If k < d, then = ∞, when n → ∞. Hence p(n) = .

Exercises 3.2-7

Proof by induction.
Base case: .
Induction case: Assume that ≥ for all i < k. Then = + ≥ + ≥ . Because φ is the root of = 0.

Exercises 3.2-6

http://en.wikipedia.org/wiki/Fibonacci_number

Exercises 3.2-5

lg *(lg n) = (lg* n) – 1 > lg (lg* n).

Exercises 3.2-4

No, it is moderated exponential, which larger than any polynomial but smaller than any exponential.
Take logarithm on any polynomial will get a constant, but = . It is not constant.
But = Θ(lg lg n lg lg lg n) = = o( lg n ). So it is polynomial bounded.