For parameters \(a\) and \(b\), both of which are \(ω(1)\), \(T(n) =…
2020
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
- A.
\(\Theta (\log_a \log _b n)\) - B.
\(\Theta (\log_{ab} n)\) - C.
\(\Theta (\log_{b} \log_{a} \: n)\) - D.
\(\Theta (\log_{2} \log_{2} n)\)
Attempted by 57 students.
Show answer & explanation
Correct answer: A
Key idea: each recursive call replaces n by n^{1/a}, so count how many calls until the argument becomes b.
After k calls the argument is n^{1/a^k}. Set n^{1/a^k} = b and take log base b to get (1/a^k)·log_b n = 1, so a^k = log_b n.
Solve for k: k = log_a(log_b n). Since T(b)=1, T(n) equals the number of calls up to b plus the base cost, so T(n) = Θ(log_a log_b n).
Remark: logarithm base changes only introduce constant factors, so expressing the result with these bases is valid in Θ-notation.
A video solution is available for this question — log in and enroll to watch it.