Project ForgeAlgorithms
Complexity Analysis
GATE 2020
Hard
For parameters a and b, both of which are ω(1), T(n) = T(n^(1/a)) + 1, and T(b) = 1. Then T(n) is
- Θ(log_a log_b n)
- BΘ(log_ab n)
- CΘ(log_b log_a n)
- DΘ(log_2 log_2 n)
Explanation
Substitute n = b^m, so m = log_b n, and define S(m) = T(b^m). Since n^(1/a) = b^(m/a), the recurrence becomes S(m) = S(m/a) + 1, bottoming out at m=1 (i.e. n=b, where T(b)=1 is given). Unrolling k times: S(m) = S(m/a^k) + k, which terminates when m/a^k = 1, i.e. k = log_a m. So S(m) = Θ(log_a m), and substituting back m = log_b n gives T(n) = Θ(log_a log_b n).
Source: GATE CS 2020 (2020)
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.