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.
On
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)$.
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)$.