Project ForgeAlgorithms
Complexity Analysis
GATE 2009
Medium
The running time of an algorithm is represented by T(n) = n for n≤3, and T(n)=T(n/3)+cn otherwise. Which one of the following represents the time complexity of the algorithm?
- Θ(n)
- BΘ(n log n)
- CΘ(n²)
- DΘ(n² log n)
Explanation
By the Master Theorem with a=1, b=3, f(n)=cn: n^(log_b a) = n^0 = 1, which f(n)=cn strictly dominates (case 3), so T(n)=Θ(f(n))=Θ(n).
Source: GATE CS 2009 (2009)
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.