3
$\begingroup$

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$

$\endgroup$
9
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ QuickSelect is $O(n)$ on average. The worst-case linear time algorithm selects recursively as pivot the median of medians, and then applies the same steps of QuickSelect. $\endgroup$ – Massimo Cafaro May 11 '12 at 5:25
  • 1
    $\begingroup$ The algorithm is not known as the selection algorithm. To be precise, it is only a selection algorithm (there are plenty of others). You could improve your answer by making the link more specific. $\endgroup$ – Juho May 11 '12 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy