Problem Session 1

Refer to the problems here.

Problem 1-1

(a)
\(\left(f_1, f_5, f_2, f_3, f_4\right)\)

This is because $ (log n)^a = o(n^b) $ for any value of a and b (proved in recitation).

(d)
Using Sterling’s approximation, $ n! = \Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right) $.
Using Sterling’s approximation in the expansion of $ nCn/2 $, we get $ nCn/2 = \Theta\left(\frac{2^n}{\sqrt{n}}\right) $
\(\left(\{f_5, f_2\}, f_3, f_1, f_4\right)\)

Problem 1-2

Obvious solution.