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
-
0What do you mean by *without using limits*? – 2011-09-18
-
0I wrote an answer then deleted it, since I think it is not what you need. Anyway, the idea is to find a bound from above for $(n+1)!$ by taking logarithms: $$\log(n+1)!\le \int_1^{n+1}\log(x+1)\, dx.$$ Evaluating the integral and then exponentiating you get the desired bound: $(n+1)!\le e(n+1) ( n+1 / e)^{n+1}$. Can this be of some help to you...? – 2011-09-18
-
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/3 = 2/3 \leq 1$. What am I missing? – 2011-09-19
-
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