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,

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