The Master Method does not apply for the recurrence T(n but the same idea—considering the summation of all the work in the recursion tree—will still work. Prove that T(n) = Θ(n log2 n) by analyzing...

The Master Method does not apply for the recurrence T(n

but the same idea—considering the summation of all the work in the recursion tree—will still work. Prove that T(n) = Θ(n log²
n) by analyzing the summation analogous to (†).