The Algorithm Design Manual (3rd) Exercise Solution 'E4-22'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-22

Question

The median of a set of n values is the $\lceil n/2 \rceil$-th smallest value.
(a) Suppose quicksort always pivoted on the median of the current sub-array. How many comparisons would quicksort make then in the worst case?
(b) Suppose quicksort always pivoted on the $\lceil n/3 \rceil$-th smallest value of the current sub-array. How many comparisons would be made then in the worst case?

Solution

Subproblem (a)

In a partition part of Quicksort, the algorithm does n comparisons.
The fact that the pivot is always median indicates that a partitioning produces two half-length arrays of their original array, which is an ideal case of Quicksort.
So the number of repetition is $\lg{n}$ and the total number of comparisons is $n\lg{n}$.

Subproblem (b)

A partition produces a $\frac{1}{3}$-length array and a $\frac{2}{3}$-length array of their original array.
So let h be a number of repetition (that is also the height of Quicksort recursion tree).
Then, the following equation holds:

So, the number of comparisons is approximately $1.7n\lg{n}$.