For constants \(a≥1\) and \(b>1\), consider the following recurrence defined…
2021
For constants \(a≥1\) and \(b>1\), consider the following recurrence defined on the non-negative integers:
\(T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n)\)
Which one of the following options is correct about the recurrence \(T(n)\) ?
- A.
if
\(f(n)\)is\(n \log_2(n)\), then\(T(n) \)is\(\Theta(n \log_2(n))\). - B.
if
\(f(n)\)is\(\dfrac{n}{\log_2(n)}\), then\(T(n) \)is\(\Theta(\log_2(n))\). - C.
if
\(f(n)\)is\(O(n^{\log_b(a)-\epsilon})\)for some\(\epsilon >0\), then\(T(n) \)is\(\Theta(n^{\log_b(a)})\). - D.
if
\(f(n)\)is\(\Theta(n^{\log_b(a)})\), then\(T(n) \)is\(\Theta(n^{\log_b(a)})\).
Attempted by 167 students.
Show answer & explanation
Correct answer: C
Key idea: apply the Master Theorem to compare f(n) with n^{log_b(a)}.
Write n=b^k so the recursion depth is k = log_b n.
Number of leaves = a^k = n^{log_b(a)}. If f(n) is polynomially smaller than n^{log_b(a)} (f(n)=O(n^{log_b(a)-ε})), the total cost is dominated by the leaves, giving Θ(n^{log_b(a)}).
Costs on internal levels form a lower-order geometric series under this assumption, so they do not change the leading term.
Therefore, when f(n)=O(n^{log_b(a)-ε}) for some ε>0, T(n)=Θ(n^{log_b(a)}).
A video solution is available for this question — log in and enroll to watch it.