1

I would like to show that $n^{log n} = o(2^n)$.

Here is my attempt:

I see that $\log{(n^{\log{n}})} = (\log{n})^2,$ and $\log{2^n} = n\log{2}$. I also know that $(\log{n})^2=o(n)$, so that for any $d>0$ eventually $(\log{n})^2 < d{n}.$

So, one approach would be to let $c>0$ and try to work backwards from $n^{\log{n}} < c2^n \rightarrow (\log{n})^2 < \log{c}+n\log{2}$, and figure out what $d$ I need...but this seems unlikely since $\log{c}$ can be arbitrarily negatively large.

I also tried looking at it more generally...showing that if $\log{g(n)} = o(\log{f(n)})$, then it must be that $g(n) = o(f(n))$. But I run into the same issue as in the above concrete example.

MathStudent
  • 1,352
  • 11
  • 22
  • It's not right that $\log^2 n = o(\log n)$. – user208259 Jan 21 '15 at 19:16
  • I meant $o(n)$, it is fixed now -- thanks. – MathStudent Jan 21 '15 at 19:32
  • You started out with functions $f(n)$ and $g(n)$ for which you wanted to prove $f(n) = o(g(n))$. You took their logarithms, which amounts to writing $f(n) = e^{\log f(n)}$ and $g(n) = e^{\log g(n)}$. So proving what you want amounts to showing that $e^{\log f(n)}/e^{\log g(n)} = e^{\log f(n) - \log g(n)} \to 0$. In other words, you are to prove $\log f(n) - \log g(n) \to -\infty$. Does this clarify what you need to prove? – user208259 Jan 21 '15 at 19:49
  • Yes, now I get it -- thank you. – MathStudent Jan 21 '15 at 20:04

1 Answers1

0

It isn't to hard to show that $n^{\log n} = O(2^n)$. In fact there is a constant $M$ satisfying $0 \le (\log x)^2 \le M + x \log 2$ for all $x > 1$.

Consider the following application of L'Hospital's rule: since $\displaystyle \lim_{x \to \infty} \frac{x \log x}{2^x}$ takes the form $\dfrac{\infty}{\infty}$ you have $$\lim_{x \to \infty} \frac{x \log x}{2^x} = \lim_{x \to \infty} \frac{x \log x \cdot 2 \log x \cdot \frac 1x}{2^x \log 2}$$ provided that the latter limit exists. But since $\dfrac{x \log x}{2^x}$ is bounded above and below (provided say $x > 1$) and $\dfrac{\log x}{x} \to 0$, you may conclude that $$\lim_{x \to \infty} \frac{x \log x \cdot 2 \log x \cdot \frac 1x}{2^x \log 2} = 0.$$

Umberto P.
  • 52,165