How to prove $n^{\log n}$ is $\mathcal{O}(2^n)$?

Question

I've seen proofs here that help with $n\log n = \mathcal{O}(n^2)$. However, if we take it a step further, how could one prove $n^{\log n}$ is $ \mathcal{O}(2^n)$?

We are assuming $n\in\mathbb{N}$. Would it extend to $n\in (0,\infty)$?

If we apply limit of $x\rightarrow\infty$, the final limit achieved is $\infty$ itself (after applying exponent rule). So how do I start my logic to make this proof?

Any help is greatly appreciated.

Are you sure that $\lim_{n\to\infty}\dfrac{n^{\log n}}{2^n}\to\infty$? WolframAlpha disagrees. — an4s, Jul 09 '20 at 01:55
Oh maybe that's mistake on my part. If it's 0, how to proceed then? — shiv, Jul 09 '20 at 01:58
If you get $0$, then you are done. That shows that $n^{\log n}\in\mathcal O\left(2^n\right)$. — an4s, Jul 09 '20 at 02:00
It shows that the denominator (i.e., $2^n$) grows faster than the numerator (i.e., $n^{\log n}$). If $f(n) \ll g(n)$, then $\dfrac{f(n)}{g(n)}\approx 0$. E.g., $\dfrac{10}{10^{10}}\approx 0$. — an4s, Jul 09 '20 at 02:12

paulinho · Accepted Answer · 2020-07-09T15:05:57.473

1

For simplicity, assuming the logarithm is in base $2$ (it doesn't really matter what base the logarithm is, because they differ by a constant), you can also note that $$\frac{n^{\log n}}{2^n} = \frac{2^{\log^2 n}}{2^n} = 2^{\log^2 n - n}$$ Since the function $2^x$ tends to $0$ as $x \to -\infty$, and since $\log^2 n = o(n)$, it follows that the exponent is $-\Theta(n)$ and namely, it tends to negative infinity. This means that the above ratio tends to zero as $n \to \infty$, so we can indeed conclude that $n^{\log n} = O(2^n)$.

edited Jul 09 '20 at 15:05

answered Jul 09 '20 at 04:36

paulinho

6,553

Usually, $\log n$ is the natural logarithm (base $e$). No need to assume: taking logarithm will yield the result: $\log \frac{n^{\log{n}}}{2^n}= \log^2n-n\log 2$. – farruhota Jul 09 '20 at 05:48
@farruhota That's correct; I meant to assume that just so the calculations would be a little cleaner. I'll add a clarification – paulinho Jul 09 '20 at 15:05
no problem, good answer +1 – farruhota Jul 09 '20 at 15:07
@farruhota Sure, I can add that. What am I allowed to assume? Can I assume $\log n$ grows smaller than $n^p$ for positive $p$? – paulinho Jul 09 '20 at 15:10
nevermind, the asker has already accepted, so I think s/he is satisfied. Good luck. – farruhota Jul 09 '20 at 15:11

score 0 · Answer 2 · answered Jul 09 '20 at 02:06

There's a master lemma I find useful for such problems:

If $\log f(n) = o(\log g(n))$, then $f(n) = o(g(n))$, and therefore in particular $f(n) = O(g(n))$.

(It's not true that $\log f(n) = O(\log g(n))$ implies $f(n) = O(g(n))$, as the example $f(n)=n^2$ and $g(n)=n$ shows.)

If you can prove that $\log(2^n) = o(\log(n^{\log n}))$, this lemma then implies that $2^n = o(n^{\log n})$ and thus that $n^{\log n} \ne O(2^n)$.

How to prove $n^{\log n}$ is $\mathcal{O}(2^n)$?

2 Answers2