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 Stirling’s approximation, $n! = \Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$.
Using Stirling’s approximation in the expansion of $\binom{n}{n/2}$, we get $\binom{n}{n/2} = \Theta\left(\frac{2^n}{\sqrt{n}}\right)$.
Problem 1-2
Obvious solution.