# Could anyone prove why O(n^(log n)) < O((log n)^n)?

Could someone provide a rigorous proof of why $$O(n^{log n}) \leq O((\log n)^n)$$ is true? I'm trying to do this by induction but it isn't working. Thanks.

• Compare the logarithms of these two functions – diplodoc Oct 6 '19 at 6:19

Using $$<$$ with the big-oh notation is a bit of abuse of notation. Formally, I take your statement to mean $$\forall f(n) \in O(n^{\log n}), \; f(n) \in O((\log n)^n)$$.

Let $$f(n) \in O(n^{\log n})$$, by definition of big-oh we know that the function is eventually bounded from above by $$c n^{\log n}$$ for some constant $$c > 0$$. Then, for sufficiently large $$n$$, $$f(n) \le c n^{\log n} = c 2^{\log(n^{\log n})} = c2^{\log^2 n} < c2^n < c (\log n)^n,$$ showing that $$f(n) \in O((\log n)^n)$$.

In particular the constant c in the last term can be made arbitrarily small. Indeed $$n^{\log n} \in o((\log n)^n)$$. A simple way to see this is by taking the limit of the ratio of the two functions:

$$\lim_{n \to \infty} \frac{n^{\log n}}{(\log n)^n} = \lim_{n \to \infty} \frac{2^{\log^2 n}}{2^{n \log n}} = 2^{\lim_{n \to \infty} \log^2 n - n \log n} = 0$$

• +1 for mentioning the ambiguity of $<$. – WhatsUp Oct 6 '19 at 22:44

Try to check for large values of n Suppose n = 1000 and base of log = 10. i.e for n^(logn) = (1000)^3 = 1000000000
(logn)^n = (3)^100 = 5.1537752e+47

Thus results are speaking for itself.

• That is not a rigorous proof. – ttnick Oct 6 '19 at 11:20
• That's not a rigorous proof, but it shows intuitively that it might be true. It could be the first step of such a way of thought. This example accompanied by limits would be quite better. – Rafael Campos Nunes Oct 7 '19 at 14:23