Solve the following recurrence equation Solve the following

Solve the following recurrence equation

Solve the following recurrence equation. You may assume that n is a power of 2. T(n) = 2 T(n/2) + n log(n/2) for n > 2 T(2) = 1 Note that the master theorem is not applicable. FYI: this is the recurrence equation describing the running time (worst case) of a version of the two-dimensional closest-pair algorithm in which we sort each of the two sets of points in ascending order of their y coordinates on each recursive call. Assuming that sorting is done using mergesort, this leads to the recurrence T(n) = 2 T(n/2) + 2n/2 log(n/2).

Solution

We know that T(1) = 1 and this is a way to end the derivation above. In particular we want T(1) to appear on the right hand side of the = sign. This means we want:

Continuing with the previous derivation we get the following since k = log₂ n: