I have started to learn about asymptotic notations, and I was asked to prove that:
$$c_1(\log_2(n))! \leq n^3 \leq c_2(\log_2(n))!$$
where $c_1$,$c_2$ are constants. I have tried for a really long time to solve it, but I have no clue how to deal with $(\log_2(n))!$
Could someone help please?
Using Sterling's formula, we have $$\begin{align} (\log_2n)! &\approx \sqrt{2\pi\log_2n}\left(\frac{\log_2n}e\right)^{\log_2n} \\ &= \frac{(\log_2n)^{\log_2n}}{n^{\log_2e}}\sqrt{2\pi\log_2n} \\ \end{align}$$ We can write $(\log_2n)^{\log_2n}$ as a power of $n$ by noting that $$n^{f(n)}=(\log_2n)^{\log_2n} \iff f(n)=\log_2(\log_2n)$$ Hence $$\begin{align} (\log_2n)! &\approx a_1n^{\log_2(\log_2n)-a_2}\sqrt{\log_2n} \\ &\gg n^3 \quad \text{as}\;n\rightarrow\infty \end{align}$$ where $a_1,a_2$ are constants. This means that your original inequality can't be true for asymptotic $n$.