Project ForgeAlgorithms
Complexity Analysis
GATE 2017
Hard
Consider the recurrence function T(n) = 2T(√n) + 1, for n > 2, and T(n) = 2 for 0 < n ≤ 2. Then T(n) in terms of Θ notation is
- AΘ(log log n)
- Θ(log n)
- CΘ(√n)
- DΘ(n)
Explanation
Substitute n = 2^m, so √n = 2^(m/2). Let S(m) = T(2^m); then S(m) = 2·S(m/2) + 1. By the Master Theorem, a=2, b=2, f(m)=1=O(m^(log₂2 − ε)), so S(m) = Θ(m^(log_b a)) = Θ(m). Since m = log₂n, T(n) = Θ(log n).
Source: GATE CS 2017 (Session 2) (2017)
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.