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.

  • 2
    $\begingroup$ Compare the logarithms of these two functions $\endgroup$ – 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 $$

  • $\begingroup$ +1 for mentioning the ambiguity of $<$. $\endgroup$ – 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.

  • $\begingroup$ That is not a rigorous proof. $\endgroup$ – ttnick Oct 6 '19 at 11:20
  • $\begingroup$ 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. $\endgroup$ – Rafael Campos Nunes Oct 7 '19 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.