1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ One way or the other you'll need to understand that $\frac{n^n}{n!}$ behaves like $e^n$, i.e. it blows up. This can be done directly or by quoting Stirling's formula. $\endgroup$
    – Ian
    Oct 15, 2016 at 23:38

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I'm having trouble understanding why $\frac{n!}{n} \leq \frac{1}{n}$ $\endgroup$
    – jeanluc
    Oct 17, 2016 at 3:17
  • $\begingroup$ Sorry I mean $n^n$ $\endgroup$
    – jeanluc
    Oct 17, 2016 at 3:17
  • $\begingroup$ @jeanluc sorry for late reply. $\frac{n!}{n^n} = \frac{1}{n}* \frac{2*3*...*n}{n^{n-1}} < \frac{1}{n}$. $\endgroup$
    – S. Y
    Oct 17, 2016 at 17:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .