Which one of the following correctly determines the solution of the recurrence relation with $T(1) = 1$? $$T(n) = 2T\left(\frac{n}{2}\right) + \log n$$

Given the recurrence relation:

Applying the Master Theorem for divide-and-conquer recurrences of the form $T(n) = aT(n/b) + f(n)$:

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

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

Comparing $f(n)$ with $n^{\log_b a}$:

• $f(n) = \log n = O(n^{1 - \epsilon})$ for any $\epsilon > 0$ (e.g., $\epsilon = 0.5$).

This falls under Case 1 of the Master Theorem, which gives:

Thus, option (A) is correct.