Project ForgeAlgorithms
Complexity Analysis
GATE 2008
Hard
Let f(n)=2ⁿ, g(n)=n!, and h(n)=n^(log n). Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?
- Af(n) = O(g(n)); g(n) = O(h(n))
- Bf(n) = Ω(g(n)); g(n) = O(h(n))
- Cg(n) = O(f(n)); h(n) = O(f(n))
- h(n) = O(f(n)); g(n) = Ω(f(n))
Explanation
n! grows faster than 2ⁿ (factorial beats exponential), so f(n)=O(g(n)) and g(n)=Ω(f(n)). Comparing h(n)=n^(log n)=2^((log n)²) to f(n)=2ⁿ: since (log n)² grows much slower than n, h(n)=O(f(n)). So the true statement is: h(n)=O(f(n)) and g(n)=Ω(f(n)) — option (D).
Source: GATE CS 2008 (2008)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.