42

Wikipedia states that the average runtime of quickselect algorithm (Link) is O(n). However, I could not clearly understand how this is so. Could anyone explain to me (via recurrence relation + master method usage) as to how the average runtime is O(n)?

4 Answers 4

63

Because

we already know which partition our desired element lies in.

We do not need to sort (by doing partition on) all the elements, but only do operation on the partition we need.


As in quick sort, we have to do partition in halves *, and then in halves of a half, but this time, we only need to do the next round partition in one single partition (half) of the two where the element is expected to lie in.

It is like (not very accurate)

n + 1/2 n + 1/4 n + 1/8 n + ..... < 2 n

So it is O(n).

Half is used for convenience, the actual partition is not exact 50%.

7
  • 4
    in the worst-case it's O(n^ 2)
    – simpatico
    May 23, 2012 at 16:03
  • 4
    dante - average case is O(n), worst case is O(n^2), because as you said the partition is not guaranteed to be 50%. eg. in a 10 element array in the case where you select the worst possible partition each time you'll end up with n + 9/10n + 8/10n + ... + 1/10n i.e. n^2. See en.wikipedia.org/wiki/Selection_algorithm for a more detailed explanation.
    – shreddd
    Dec 28, 2012 at 22:31
  • It would be exactly n/2 if the partition was guaranteed to be 50%. Using the sum of a geometric progression formula a1/(1 - q)
    – Tito
    Nov 2, 2013 at 15:59
  • 1
    @shreddd But isn't big Oh only used for measuring worst case? Mar 15, 2015 at 0:37
  • 3
    @committedandroider No, it's used to classify functions which grow maximally with a certain asymptotic speed. So in this case it means that the expected value (on input uniformly at random) of the runtime doesn't grow faster than the function c*n for some constant c. Feb 24, 2016 at 18:41
40

To do an average case analysis of quickselect one has to consider how likely it is that two elements are compared during the algorithm for every pair of elements and assuming a random pivoting. From this we can derive the average number of comparisons. Unfortunately the analysis I will show requires some longer calculations but it is a clean average case analysis as opposed to the current answers.

Let's assume the field we want to select the k-th smallest element from is a random permutation of [1,...,n]. The pivot elements we choose during the course of the algorithm can also be seen as a given random permutation. During the algorithm we then always pick the next feasible pivot from this permutation therefore they are chosen uniform at random as every element has the same probability of occurring as the next feasible element in the random permutation.

There is one simple, yet very important, observation: We only compare two elements i and j (with i<j) if and only if one of them is chosen as first pivot element from the range [min(k,i), max(k,j)]. If another element from this range is chosen first then they will never be compared because we continue searching in a sub-field where at least one of the elements i,j is not contained in.

Because of the above observation and the fact that the pivots are chosen uniform at random the probability of a comparison between i and j is:

2/(max(k,j) - min(k,i) + 1)

(Two events out of max(k,j) - min(k,i) + 1 possibilities.)

We split the analysis in three parts:

  1. max(k,j) = k, therefore i < j <= k
  2. min(k,i) = k, therefore k <= i < j
  3. min(k,i) = i and max(k,j) = j, therefore i < k < j

In the third case the less-equal signs are omitted because we already consider those cases in the first two cases.

Now let's get our hands a little dirty on calculations. We just sum up all the probabilities as this gives the expected number of comparisons.

Case 1

Case 2

Similar to case 1 so this remains as an exercise. ;)

Case 3

We use H_r for the r-th harmonic number which grows approximately like ln(r).

Conclusion

All three cases need a linear number of expected comparisons. This shows that quickselect indeed has an expected runtime in O(n). Note that - as already mentioned - the worst case is in O(n^2).

Note: The idea of this proof is not mine. I think that's roughly the standard average case analysis of quickselect.

If there are any errors please let me know.

9
  • Thanks, that was the rigorous answer I was looking for.
    – Kuba
    Feb 2, 2017 at 18:32
  • There is a mistake in your analysis of Case 1. $\sum _{d=1}^{k-1} \neq \sum _{d=1} ^{k-1} \frac{d}{d+1} $
    – john doe
    Jan 21, 2018 at 22:06
  • @johndoe I'm afraid I don't understand. Do you refer to the equality after the line break in the analysis of case 1? This comes from $\frac{d}{d+1} = \frac{d+1}{d+1} - \frac{1}{d+1} = 1 - \frac{1}{d+1}$. Feb 7, 2018 at 23:56
  • @maybeshewill I meant the equality just before that
    – john doe
    Feb 8, 2018 at 14:49
  • @johndoe This is just "inverting" the sum. For the left side the first term of the sum is (k-1)/(d+1) and the last one 1/(d+1); for the right side the first term is 1/(d+1) and the last one is (k-1)/(d+1). Thus, the sums are equal. Feb 12, 2018 at 23:57
14

In quickselect, as specified, we apply recursion on only one half of the partition.

Average Case Analysis:

First Step: T(n) = cn + T(n/2)

where, cn = time to perform partition, where c is any constant(doesn't matter).
T(n/2) = applying recursion on one half of the partition.
Since it's an average case we assume that the partition was the median.

As we keep on doing recursion, we get the following set of equation:

T(n/2) = cn/2 + T(n/4)
T(n/4) = cn/2 + T(n/8)
.
.
.
T(2) = c.2 + T(1)
T(1) = c.1 + ...

Summing the equations and cross-cancelling like values produces a linear result.

c(n + n/2 + n/4 + ... + 2 + 1) = c(2n) //sum of a GP

Hence, it's O(n)

1
  • 4
    This is no average case analysis. For an average case analysis you have to consider every possible pivoting and not only the expected value of the pivot element. Sep 11, 2014 at 17:48
3

I also felt very conflicted at first when I read that the average time complexity of quickselect is O(n) while we break the list in half each time (like binary search or quicksort). It turns out that breaking the search space in half each time doesn't guarantee an O(log n) or O(n log n) runtime. What makes quicksort O(n log n) and quickselect is O(n) is that we always need to explore all branches of the recursive tree for quicksort and only a single branch for quickselect. Let's compare the time complexity recurrence relations of quicksort and quickselect to prove my point.

Quicksort:

T(n) = n + 2T(n/2)
     = n + 2(n/2 + 2T(n/4))
     = n + 2(n/2) + 4T(n/4)
     = n + 2(n/2) + 4(n/4) + ... + n(n/n)
     = 2^0(n/2^0) + 2^1(n/2^1) + ... + 2^log2(n)(n/2^log2(n))
     = n (log2(n) + 1)      (since we are adding n to itself log2 + 1 times)

Quickselect:

T(n) = n + T(n/2)
     = n + n/2 + T(n/4)
     = n + n/2 + n/4 + ... n/n
     = n(1 + 1/2 + 1/4 + ... + 1/2^log2(n))
     = n (1/(1-(1/2))) = 2n                           (by geometric series)

I hope this convinces you why the average runtime of quickselect is O(n).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.