is (n+1)! in the order of (n!)? can you show me a proof?

Question

What about (n-1)!?

Also if you could show me a proof that would help me understand better.

I'm stuck on this one.

Answer 1

To show that (n+1)! is in O(n!) you have to show that there is a constant c so that for all big enough n (n > n0) the inequality

(n+1)! < c n!

holds. However since (n+1)! = (n+1) n! this simplifies to

n+1 < c

which clearly does not hold since c is a constant and n can be arbitrarily large.

On the other hand, (n-1)! is in O(n!). The proof is left as an exercise.

Answer 2

(n+1)! = n! * (n+1)

O((n+1)*n!) = O(nn!+n!) = O(2(nn!)) = O(n*n!) > O(n!)

(n-1)! = n! * n^-1

O(n-1)! = O(n!/n) < O(n!)