patternMinor
Could anyone prove why O(n^(log n)) < O((log n)^n)?
Viewed 0 times
anyonewhylogcouldprove
Problem
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.
Solution
Using $ 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
$$
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
$$
Context
StackExchange Computer Science Q#115490, answer score: 6
Revisions (0)
No revisions yet.