Solutions to Assignment 1

O is an upper bound. To say that something has an upper bound of "at least" x means it could be less than x or it could be more than x. It's like if you ask someone "Do you know the upper bound" and the response is "Maybe I do and maybe I don't."

Exercise 2.1-4.

2ⁿ⁺¹ = O(2ⁿ) because 2ⁿ⁺¹ = 2 * 2ⁿ = O(2ⁿ).

Suppose 2²ⁿ = O(2ⁿ) Then there exists a constant c such that for n beyond some n₀, 2²ⁿ <= c 2ⁿ. Dividing both sides by 2ⁿ, we get 2ⁿ < c. There's no values for c and n₀ that can make this true, so the hypothesis is false and 2²ⁿ != O(2ⁿ).

Problem 2-2

A	B	O	o		w
lgk n	n	yes	yes	no	no	no
nk	cn	yes	yes	no	no	no
n1/2	nsin n	no	no	no	no	no
2n	2n/2	no	no	yes	yes	no
nlg m	mlg n	yes	no	yes	no	yes
lg n!	lg nn	yes	no	yes	no	yes

Problem 2-3.

We are to rank the functions given in order of increasing asymptotic growth. Here is my ranking. Functions on the same line are in the same equivalence class, i.e., theta of each other. If you get most of them in the right order, you'll get full credit.

1, n^1/lgn
lg*(lg n)
lg(lg* n)
lg *n
ln ln n
sqrt(lg n)
ln n, 2^{lg* n}
lg²n, (lg n)!
(lg n)^{lg n}
sqrt(2)^{lg n}
2^{sqrt(2 lg n)}
n, 2^{lg n}
n lg n, lg (n!)
4^{lg n}, n²
n³
(3/2)ⁿ
2ⁿ
eⁿ
n 2ⁿ
2²ⁿ
2²ⁿ⁺¹
n!
(n+1)!