TADM2E 4.17

Part A

Always choosing the median splits the halves evenly, resulting in log(n) passes, with each pass having n compares. The total would be n log(n).

Part B

Let F(n) be the number of compares for a quicksort of size n, split into a section of size 1/3 and a section of size 2/3. The recurrence relation would be:

F(n) = n/3 + 2n/3 + F(n/3) + F(2n/3) = n + F(n/3) + F(2n/3)

In other words, the number of compares at size n is equal to the number of compares to do a top level partition (1/3 for one side, 2/3 for the other side), plus the number of compares to quicksort the 1/3 partition and the 2/3 partition.

Upper bound appoximation

One way to get an upper bound for the number of compares is to assume that there are N compares at all levels, and use the maximum partition depth. The maximum partition depth is the depth of the worst case 2/3 partition.

For a 1/2 partition, you would expect a depth of log[base2](n), but for a 2/3 partition, you would expect a depth of log[base3/2](n). Switching from log of base 3/2 to log of base 2 yields:

log[base3/2](n) = log[base2](n) / log[base2](3/2) ~= log[base2](n) / 0.585 = 1.71 log(n)

So one upper bound would be 1.71 n log(n).