Consider the following functions: f(n) = 2^n g(n) = n! h(n) = n^(log n) Which…
2008
Consider the following functions:
f(n) = 2^n
g(n) = n!
h(n) = n^(log n)
Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
- A.
f(n) = O(g(n)); g(n) = O(h(n))
- B.
f(n) = Ω(g(n)); g(n) = O(h(n))
- C.
g(n) = O(f(n)); h(n) = O(f(n))
- D.
h(n) = O(f(n)); g(n) = Ω(f(n))
Attempted by 183 students.
Show answer & explanation
Correct answer: D
Correct answer: Option D.
Given f(n) = 2^n, g(n) = n!, and h(n) = n^(log n).
First compare h(n) with f(n). Taking log base 2 for simplicity, n^(log n) = 2^((log n)^2). Since (log n)^2 = o(n), we get 2^((log n)^2) = O(2^n). Hence h(n) = O(f(n)).
Now compare g(n) with f(n). By Stirling's approximation, n! ~ sqrt(2*pi*n)(n/e)^n, so n!/2^n ~ sqrt(2*pi*n)(n/(2e))^n, which tends to infinity. Hence n! = Ω(2^n), so g(n) = Ω(f(n)).
Therefore h(n) = O(f(n)) and g(n) = Ω(f(n)), which matches option D. Options A and B fail because n! is not O(n^(log n)), and option C fails because n! is not O(2^n).
A video solution is available for this question — log in and enroll to watch it.