¿Cómo hace uno para mostrar que $n^n \notin O((n+1)!)$ sin el uso de límites? Recientemente he estado tratando de demostrar que estos resultados, sin límites, y este es un caso que se me sigue molestando.
Respuesta
¿Demasiados anuncios?
No estoy seguro de lo que quieres decir por "sin el uso de límites" desde la Notación Big O , por definición, implica un límite.
En cualquier caso, tenga en cuenta que para todas las $n \geq 1$
$$ \frac{n^n}{(n+1)!} = \frac{n}{2} \frac{n}{3} \cdots \frac{n}{n+1} > \frac{n}{4}, $$
por lo tanto, claramente $n^n \notin O((n+1)!)$.
(El muy crudo bound yo uso proviene de considerar sólo el primero y el último término en el producto y el hecho de que $n/k \geq 1$ por cada $k \in \{3,\ldots,n\}$.)
