Factorial

O(n!) ~ O(nlogn)

The actual proof is difficult.

The simple solution is:

n! = n . n-1. n-2.... n/2. n/2-1...1

n! > (n/2)^n/2

O(n!) > O(n/2)^n/2

O(log(n!)) > O(log(n/2)^n/2)

O(log(n!)) > O(n/2 log(n/2))

O(log(n!)) > O(n log(n))