# data structures – Quicksort with median as pivot

Suppose we use the median as a pivot in Quicksort, and suppose we can compute the median in linear time.

We can estimate the number of comparisons $$C(n)$$ performed by this modified version of Quicksort as
$$C(n) leq begin{cases} 2C(lfloor n/2 rfloor) + Dn, & text{if } n geq 2, quad text{(D is some positive constant)} \ 1, & text{if } n leq 1, end{cases}$$
where the term $$2C(lfloor n/2 rfloor)$$ is the number of comparisons incurred by the two recursive calls, and
the linear expression $$Dn$$ is an upper bound on the number of comparisons incurred by median search, partitioning the input array $$A$$.

Using the method of backward substitution and assuming $$n$$ is the power of 2,

1. What will be the closed-form solution for $$C$$?
2. What is big $$O$$ of this modified version of Quicksort?
3. If the median were a quadratic function of the array size, what will be the new big $$O$$?