Order of magnitudes comparasions I have a list of order of magnitudes I want to compare.
My only idea is using calculus methods (limits , integral, etc...) to assert the functions relation.
I need your help with the following.
I need to determine (again by order of magnitude) how to order the following (by asceneding order):
$log(n) / log(log(n))$
$log(log(n))$
$log^3(n)$
$n/log(n)$
$n^{log(n)}$
Is it even possible to use limits on such functions?
I mean if I take $f(n)$ to be $log(n) / log(log(n))$ and $g(n)$ to be $n^{log(n)}$, It seems very hard to find out the limit.
Thanks in advance!
 A: There are quite a number of comparisons to be made. It is in most cases relatively straightforward to decide about the relative long-term size.
Let's start with your pair. We have $f(n)=\log(n)/\log(\log (n))$ and $g(n)=n^{\log(n)}$. 
For large $n$ (and it doesn't have to be very large), we have $f(n)\lt \log(n)$.
Also, for large $n$, we have $\log(n)\gt 1$, and therefore $g(n)=n^{\log(n)}\gt n$.
So for large $n$, we have
$$\frac{f(n)}{g(n)} \lt \frac{\log(n)}{n}.$$
But we know that $\lim_{n\to\infty}\dfrac{\log(n)}{n}=0$.  This can be shown in various ways. For instance, we can consider $\dfrac{\log(x)}{x}$ and use L'Hospital's Rule to show this has limit $0$ as $x\to\infty$.
It takes less time to deal with the pair $n/\log(n)$ and $n^{\log(n)}$. If $n$ is even modestly large, we have $n/\log(n)\lt n$. But after a while, $\log(n)\gt 2$, so $n^{\log(n)}\gt n^2$. It follows that in the long run, $n^{\log(n)}$ grows much faster than $n/\log(n)$.
As a last example, let us compare $\log^3(n)$ and $n/\log(n)$. Informally, $\log$ grows glacially slowly. More formally, look at the ratio $\dfrac{\log^3(n)}{n/\log(n)}$. This simplifies to 
$$\frac{\log^4 (n)}{n}.$$
We can use L'Hospital's Rule on $\log^4(x)/x$. Unfortunately we then need to use it several times.
It is easier to examine $\dfrac{\log(x)}{x^{1/4}}$. Then a single application of L'Hospital's Rule does it. Or else we can let $x=e^y$. Then we are looking at $y^4/e^y$, and we can quote the standard result that the exponential function, in the long run, grows faster than any polynomial. 
Remark: The second person in your list is the slowest one. Apart from that, they are in order. So you only need to prove four facts to get them lined up. A fair part of the work has been done above. 
A: For instance:
$$\log(n^{\log n})=\log^2(n)$$
And since asymptotically:
$$\frac{\log(n)}{\log(\log(n))} < \log^2(n)$$
We know that:
$$n^{\log n}$$
Is at least exponentially larger than:
$$\frac{\log(n)}{\log(\log(n))}$$
A: @André Nicolas
I really liked the comprasion of the functions with simplier functions.
I was trying to use this technique on some of these functions.
Eventually I found a couple which I was not able to solve using this technique and I don't understand why.
Assume $f(n) = log(log(n))$ and $g(n) = n/log(n)$
Now one might say, $f(n) < log(n)$ and $g(n) > 1/n$
If I look at the ratio/limit of $f(n)/g(n)$, I find out that $f(n)$ is much faster.
I completly understand that I chose unwisely the lower bound of g(n). Does it mean that on such functions I cannot use this technique?
Thank you in advance!!
