Big-O estimates for the factorial function and the logarithm of the factorial…
2014
Big-O estimates for the factorial function and the logarithm of the factorial function i.e. n! and log n! is given by
- A.
O(n!) and O(n log n)
- B.
O(nn) and O(n log n)
- C.
O(n!) and O(log n!)
- D.
O(nn) and O(log n!)
Attempted by 386 students.
Show answer & explanation
Correct answer: B
Answer: n! = Theta(n!) and log(n!) = Theta(n log n). In Big-O form: n! = O(n!) and log(n!) = O(n log n).
Reasoning (upper and lower bounds):
Upper bound for log(n!): log(n!) = sum_{k=1}^{n} log k ≤ n log n, so log(n!) = O(n log n).
Lower bound for log(n!): sum the last half of the terms: for k from ⌈n/2⌉ to n, each log k ≥ log(n/2), giving log(n!) ≥ (n/2) log(n/2) = Theta(n log n).
Combining the bounds yields log(n!) = Theta(n log n), so the simplified Big-O is O(n log n).
Comment on n!: Saying n! = O(n^n) is true but loose because n! ≤ n^n. The tight and conventional expression is n! = Theta(n!) (or simply O(n!)).