Question

For constants \(a \geq 1\) and \(b > 1\), consider the following recurrence defined on the non-negative integers:
\[ T(n) = a \cdot T\!\left(\frac{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 \(\frac{n}{\log_2(n)}\), then \(T(n)\) is \(\Theta(\log_2(n))\).
• C. If \(f(n)\) is \(O\!\left(n^{\log_b(a)-\varepsilon}\right)\) for some \(\varepsilon > 0\), then \(T(n)\) is \(\Theta\!\left(n^{\log_b(a)}\right)\).
• D. If \(f(n)\) is \(\Theta\!\left(n^{\log_b(a)}\right)\), then \(T(n)\) is \(\Theta\!\left(n^{\log_b(a)}\right)\).

Hint:

Always compare \(f(n)\) with \(n^{\log_b(a)}\) to determine which case of the Master Theorem applies.

Answer 1

The Correct Option is C

Step 1: Recall the Master Theorem.
For the recurrence \(T(n) = aT(n/b) + f(n)\), define \(n^{\log_b(a)}\) as the critical function.

Step 2: Analyze option (C).
If \(f(n) = O\!\left(n^{\log_b(a)-\varepsilon}\right)\) for some \(\varepsilon > 0\), then \(f(n)\) grows polynomially slower than \(n^{\log_b(a)}\).

Step 3: Apply Case 1 of the Master Theorem.
Under this condition, the solution to the recurrence is dominated by the recursive term, yielding:
\[ T(n) = \Theta\!\left(n^{\log_b(a)}\right). \]

Step 4: Eliminate incorrect options.
Options (A), (B), and (D) do not hold in general without additional constraints on \(a\) and \(b\).

Step 5: Conclusion.
Hence, option (C) is the correct statement.

Final Answer: (C)