I'm having trouble proving that $n^2 + n!$ is not $\Theta(n^n)$. So far I was able to prove $O(n^n)$ by realizing that $n^2 \leq n^n$ and $n! \leq n^n$, and therefore their sum is less than or equal to $2n^n$. Based on graphs, I think that is is not $\Omega(n^n)$ but I'm not sure how to go about formally proving that. Any help would be much appreciated.
[Math] Prove $n^2 + n!$ is or is not $\Theta (n^n)$
asymptoticscomputer scienceproof-verification
Best Answer
You don't need any complicated formula, as this is straightforward: $$\frac{n^2+n!}{n^n} \le n^{2-n} + \frac{1}{n},$$ which will converge to zero.