Arrange in increasing order of their Big Oh Complexity

Question

So if given

4n^2, log3(n), 20n, n^2.5, log(n!), n^n, 3^n, n log (n), 100n^(2/3), 2^n, 2^(n+1), n!, (n-1)!, 2^2n

The order (increasing order of their big O complexity) would be

log3(n) < 20n < n logn < 4n^2 < 100n^(2/3) < log(n!) < n^(2.5) < 2^n < 2^(n+1) < 3^n < 2^(2n) < (n-1)! < n^n < n!

this is when n is a large number. Is that right?

Answer 1

To sum up, as n tends to +infinite, in terms of big Oh complexity:

log3(n) < 100n^(2/3) < 20n < log(n!) < n log(n) < 4n^2 < n^(2.5) < 2^n ~ 2^(n+1) < 3^n < 2^(2n) < (n-1)! < n! < n^n

This Wikipedia page may interest you.

EDIT: regarding n! vs. n^n

Using Stirling's approximation, we have:

therefore O(n!) ~O(sqrt(n) * n^n * e^(-n))
hence O(sqrt(n)) ~ O(e^(-n)) iff O(n^n) ~ O(n!).
But O(sqrt(n)) ~ O(e^(-n)) is false.
Therefore O(n^n) ~ O(n!) is false.
Since n! < n^n, we have n! = o(n^n). QED.


Here is another proof from djfm which does not rely on Stirling's approximation: