How does one show that $n^n \notin O((n+1)!)$ without using limits? I've recently been trying to prove such results without limits, and this is one case that is still bothering me.
Proving that $n^n \notin O((n+1)!)$
4
$\begingroup$
algebra-precalculus
algorithms
elementary-number-theory
-
0Can't you just take out a few terms of the factorial? e.g. (rough estimates) Write $n! \leq n^{n-3} \cdot 3^3 = 27 n^{n-3} = O(n^{n-2})$. – 2011-09-18
1 Answers
3
I'm not sure what you mean by "without using limits" since Big O Notation by definition involves a limit.
At any rate, note that for all $n \geq 1$
$ \frac{n^n}{(n+1)!} = \frac{n}{2} \frac{n}{3} \cdots \frac{n}{n+1} > \frac{n}{4}, $
hence, clearly $n^n \notin O((n+1)!)$.
(The very crude bound I use comes from considering just the first and last term in the product and the fact that $n/k \geq 1$ for each $k \in \{3,\ldots,n\}$.)
-
0If $n = 2$, then n^n / (n+1)! = 4 / 6 > n / 4 = 1/2. What *are* you missing? (Perhaps I'm not understanding where your doubt is coming from.) :) – 2011-09-19