What is O(log(n!)), O(n!), and Stirling’s approximation?

by

O(n!) isn’t equivalent to O(n^n). It is asymptotically less than O(n^n).

O(log(n!)) is equal to O(n log(n)). Here is one way to prove that:

Note that by using the log rule log(mn) = log(m) + log(n) we can see that:

log(n!) = log(n*(n-1)*...2*1) = log(n) + log(n-1) + ... log(2) + log(1)

Proof that O(log(n!)) ⊆ O(n log(n)):

log(n!) = log(n) + log(n-1) + ... log(2) + log(1)

Which is less than:

log(n) + log(n) + log(n) + log(n) + ... + log(n) = n*log(n)

So O(log(n!)) is a subset of O(n log(n))

Proof that O(n log(n)) ⊆ O(log(n!)):

log(n!) = log(n) + log(n-1) + ... log(2) + log(1)

Which is greater than (the left half of that expression with all (n-x) replaced by n/2:

log(n/2) + log(n/2) + ... + log(n/2) = floor(n/2)*log(floor(n/2)) ∈ O(n log(n))

So O(n log(n)) is a subset of O(log(n!)).

Since O(n log(n)) ⊆ O(log(n!)) ⊆ O(n log(n)), they are equivalent big-Oh classes.

More Related Contents:

  1. Computational complexity of Fibonacci Sequence
  2. What is O(log(n!)) and O(n!) and Stirling Approximation
  3. Finding Big O of the Harmonic Series
  4. Computing time complexity in C [closed]
  5. Calculating Big O Notation for a algorithm [duplicate]
  6. How do I prove or disprove that this function is Ω(n^1.5)?
  7. O(3^n) exponential time complexity [closed]
  8. How to solve T(n)=4T(sqrt(n/2))+n^(3/2)
  9. What is a plain English explanation of “Big O” notation?
  10. What does O(log n) mean exactly?
  11. What is the difference between Θ(n) and O(n)?
  12. Time complexity of nested for-loop
  13. Is a Java hashmap search really O(1)?
  14. Difference between Big-O and Little-O Notation
  15. Time complexity of Euclid’s Algorithm
  16. What would cause an algorithm to have O(log log n) complexity?
  17. What is pseudopolynomial time? How does it differ from polynomial time?
  18. What would cause an algorithm to have O(log n) complexity?
  19. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  20. What’s the time complexity of array.splice() in Google Chrome?
  21. Big O of JavaScript arrays
  22. Maximum single-sell profit
  23. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  24. What is the complexity of this simple piece of code?
  25. Why do we ignore co-efficients in Big O notation?
  26. Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?
  27. What is the time complexity of the sleep sort?
  28. What’s the time complexity of iterating through a std::set/std::map?
  29. Python dictionary keys. “In” complexity
  30. Argument for O(1) average-case complexity of heap insertion

Leave a Comment