I solved the following problem by plotting a graph and comparing the complexities. The picture below show the question along with my answer and the TA's corrections.
Can someone please tell me what I am doing wrong? I didn't understand the explanation given in class. When we plot several functions in a graph, the function that grows the fastest has the smallest value of y as compared to the other functions for the same value of x. At least that is the reasoning I am following. Please correct me if I am wrong.
Another thing that I don't understand is whether the factorial function is the fastest of all functions or not. I find it hard to believe. I've heard people claiming both sides. I found the following in our study material:
From this picture, it seems to me that n! is the slowest. Can someone confirm this?
Factorials aren't the fastest thing imaginable, but they are one of the fastest growing functions for this purpose, yes.
$n!$ can be re-represented with Stirling's approximation as $n! \sim (\frac{n}{e})^n \sqrt{2 \pi n}$. I'd recommend plugging this in and seeing what happens.
If we do, we find that $\ln(n)! \sim (\frac{\ln(n)}{e})^{\ln(n)} \sqrt{2 \pi \ln(n)} \geq n^{\ln(\ln(n))}$
Note also that $2^{2*\ln(n)} = e^{2*\ln(2)\ln(n)} = n^{2\ln(2)}$ The first form gives us that, as $n>\ln(n)$, we expect
$n! > 2^{n \ln(2)} > 2^{2\ln(n)}$ The question becomes where does $\ln(n)!$ fit in? Using our approximation and come calculus, you can see that $n^{\ln(\ln(n))} > 2^{2\ln(n)}$, giving
$n! > 2^{n \ln(2)} >\ln(n)!> 2^{2\ln(n)}$
For the bottom end, it's worth knowing (and you can figure it out with calculus) that for any $\epsilon >0$, $ln(n) = O(n^\epsilon)$, so $\ln(2\ln(n))<n^{.001}$ for sure.
The rest seems to be in place with your own logic, but that gives you the rationale for the correct ordering.