For constants $a \ge 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)$?

According to the Master Theorem for divide-and-conquer recurrences of the form $T(n) = a T(n/b) + f(n)$ where $a \ge 1$ and $b > 1$:

1. Case 1: If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$, then:

   $$T(n) = \Theta(n^{\log_b a})$$

2. Case 2: If $f(n) = \Theta(n^{\log_b a})$, then:

   $$T(n) = \Theta(n^{\log_b a} \log n)$$

3. Case 3: If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$, and if $a f(n/b) \le c f(n)$ for some constant $c < 1$ and sufficiently large $n$, then:

   $$T(n) = \Theta(f(n))$$

Evaluating the given choices:

• Option (A) & (B): Incorrect because the solution depends on the values of $a$ and $b$, which are unspecified constants.

• Option (C): Correct, as it is a direct statement of Case 1 of the Master Theorem.

• Option (D): Incorrect because when $f(n) = \Theta(n^{\log_b a})$, the solution is $T(n) = \Theta(n^{\log_b a} \log n)$, not $\Theta(n^{\log_b a})$.

Thus, (C) is the correct option.