We found that a recurrence describing the number of comparison operations for a merge sort is in the case where n is a power of 2. (Here and .We can generalize to when n is not a power of 2 with the recurrence

Exactly solve for this more general form of , and prove your solution is true by induction. Hint plot the first several values of , graphically. What do you find? You might find the following concept useful in your solution: what is ?

T(n) = 2T(n^2) + n - 1 T(1) = 0 T(2) = 1 T(n) =T( n 2) +T( [n/2]) + n - 1 2 logen T(n) = 2T(n^2) + n - 1 T(1) = 0 T(2) = 1 T(n) =T( n 2) +T( [n/2]) + n - 1 2 logen