Prove or disprove
a) 2n = O(2n + 1)
b) 22n = O(n!)
c) max(n2; 100n3) =
(n3)
d) if f(n) =
(g(n)) and g(n) =
(h(n)) then h(n) = O(f(n))
4. Solve the following recurrence relations by the method of your choice
a) T(n) = 1 for n = 4 and T(n) =
p
nT(
p
n) + n for n > 4
b) T(n) = aT(n ô€€€ 1) + bn for n 2 and T(1) = 1
c) T(n) = 1 for n = 1 and T(n) = 3T(n
2 ) + n log n for n > 1
5. Argue that the solution to the recurrence T(n) = T(n=3) + T(2n=3) + cn is (n lg n) by appealing to the recursion tree.