Which one of the following correctly determines the solution of the recurrence…

Solution summary: Use the Master theorem on T(n) = 2 T(n/2) + log n.

• Compute parameters: a = 2, b = 2, so n^{log_b a} = n.

• Compare f(n): f(n) = log n, which is much smaller than n; specifically f(n) = O(n^{1-ε}) for some ε (for example ε = 1/2).

• Apply Master theorem case 1: Since f(n) is polynomially smaller than n^{log_b a}, case 1 applies and T(n) = Θ(n^{log_b a}) = Θ(n).

Recursion-tree check:

• At level i there are 2^i subproblems, each contributes about log(n/2^i) = log n - i. Summing level costs over i = 0..log n - 1 gives a total Θ(n). The leaves contribute n constant-cost leaves, i.e. another Θ(n). So total work is Θ(n).

Therefore the solution of the recurrence is T(n) = Θ(n).