Quicksort to find median?

Question

Why is the worst scenario $\mathcal{O}\left(n^2\right)$ when using quicksort to find the median of a set of numbers?

• If your algorithm continually picks a number larger than or smaller than all numbers in the list wouldn't your algorithm fail? For example if the list of numbers are:

  $S = (12,75,82,34,55,15,51)$

  and you keep picking numbers greater than $82$ or less than $12$ to create sublists with, wouldn't your set always remain the same size?

• If your algorithm continually picks a number that creates sublists of $1$ why is the worst case scenario $\mathcal{O}\left(n^2\right)$? Wouldn't efficiency be linear considering that according to the Master Theorem, $d>\log_b a$?* (and therefore be $\mathcal{O}\left(n^d\right)$ or specifically in this case $\mathcal{O}\left(n\right)$)

*Where $d$ is the efficiency exponent (i.e. linear, exponential etc.), $b$ is the factor the size of problem is reduced by at each iteration, $a$ is the number of subproblems and $k$ is the level. Full ratio: $T(n) = \mathcal{O}\left(n^d\right) * (\frac{a}{b^d})^k$

Answer 1

Quicksort is for sorting, the algorithm you refer to is a selection algorithm known as Quick Select.

• Since you can only pick as pivot a number that is in the list case #1 never happens.
• Worst case is that you continually pick a number that partitions the list into 2 lists: A list with just one element and a list with $n-1$ elements, if this is the case in each iteration you only rule out a single element.

So first iteration you do $n$ operations, second iteration $n-1$ operations, third one $n-2$ operations, ... last iteration 1 operation.

Which its the sum of the first $n$ natural numbers:

$1+2+3+... +(n-2)+(n-1)+ n = n(n-1)/2$ operations = $O(n^2)$