4
$\begingroup$

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.

  • 0
    Can'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 1

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\}$.)

  • 0
    If $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