I have an answer for an asymptotic analysis, which i cannot accept. please explain me where i go wrong.

Question

We have the following function definitions:

\begin{align*}f_1 (n) &= n^{n^{\frac{1}{2}}} \\ f_2 (n) &= 2^n \\ f_3 (n) &= n^{10} 2^{\frac{n}{2}} \\ f_4 (n) &= \sum_{i=1}^{n} (i+1) \end{align*}

Easily we can say that $f_4$ has the slowest growth when compared to other functions. so its $f_4$ and then its $f_1$ as its growth is slower than $f_2$ and $f_3$. I have confusions with their solutions for $f_2,f_3$ comparisons.

$f_3$ is always greater than $f_2$ and increases very fast over time than $f_2$ but they say that $f_2 > f_3$. please check the solution which i have attached.

Their verdict: $$f_4<f_1<f_3<f_2$$

My stand: $$f_4<f_1<f_2<f_3$$

Answer 1

$f3$ is not always greater than $f2$; try it for $n = 1000$. $$ f_2(n) = 2{1000} = 2^{500} \cdot 2^{500} \\ f_3(n) = 2^{500} 1000^{10} $$ Comparing these, we need to ask "Is $1000^{10}$ larger or smaller than $2^{500}$?" Well, the first one's easy: $1000^{10} = (10^3)^{10} = 10^{30}$.

What about $2^{500}$? Well, it's $2^{4 \cdot 125} = (2^4)^{125} = 16^{125} > 10^{125}$.

Since $10^{125}$ is much larger than $10^{30}$, we see that $f_2(1000) > f_3(1000)$ (and the same kind of argument works, better and better, for $N > 1000$).

Answer 2

If you divide $f_2$ by $f_3$ it's easier to see that fraction is bigger than one for big $n$ and $f_2 > f_3$:

$$\frac{f_2}{f_3} = \frac{2^{n/2}}{n^{10}} \rightarrow \infty$$

Answer 3

If we take logarithms of both $f_{2}$ and $f_{3}$ we can see:

$$\log_{2}(f_{2})=n \text{ and } \log_{2}(f_{3})=\frac{n}{2}+10\log_{2}(n)$$

Comparing $f_{2}$ and $f_{3}$ we can see that $\exists n \gg 1$ such that $\frac{n}{2}>10\log_{2}(n)$. Indeed more explicitly we can see that for any $\{n\in\mathbb{Z} : n > 144\}$ we have $\log_{2}(f_{2})>\log_{2}(f_{3})$. Which because $\log_{2}$ is a monotonically increasing function corresponds to what they state.