Question 23

Given recurrence:

with $T(1) = 1$.

1. Identify Master Theorem Parameters ($T(n) = a T(n/b) + f(n)$):

   • $a = 2$
   • $b = 2$
   • $f(n) = \log n$

2. Compute Critical Exponent:

   $$n^{\log_b a} = n^{\log_2 2} = n^1 = n.$$

3. Compare $f(n)$ with $n^{\log_b a}$:

   • $f(n) = \log n$.
   • For any $\epsilon$ such that $0 < \epsilon < 1$ (for example, $\epsilon = 0.5$):
     $$\log n = O(n^{1 - \epsilon}) = O(n^{0.5}).$$
   • Thus, $f(n)$ is polynomially smaller than $n^{\log_b a}$.

4. By Case 1 of the Master Theorem:

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

This matches option A.