Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

Question

Wikipedia here https://en.m.wikipedia.org/wiki/Selection_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The point which is unclear is whether K is required to be constant or at least independent of size of N.

I saw this issue being discussed on this site here : https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on But people there in the comments seem to claim that K is fixed.

The point which I don't understand is, if k is indeed needed to be fixed.. then what's the point of this algorithm of select and quicksort?

Why can't we just perform like bubble sort K times if K is fixed it wouldn't be more than K*N which is O(n) . So what's the problem of achiving it in O(n) if k is fixed.

Answer 1

There is no requirement that $k$ be constant, and those StackOverflow comments are misleading or simply incorrect.

Obviously $k \le n$ and so $k$ is $O(n)$. Your partial bubblesort algorithm is $O(kn)$ which is $O(n^2)$ unless $k$ is somehow restricted.

But the Quickselect algorithm is stochastic $O(n)$ and can be made worst-case $O(n)$ by using the median-of-medians algorithm to select the pivot. (Median-of-medians is too slow for practical use, but it proves that $O(n)$ is possible.) Quickselect does not require $k$ to be fixed.

Answer 2

The algorithm that uses "sort of quicksort" to find the $k$-th smallest (or largest) element is generally called quickselect.

Here is the precise meaning of "the average complexity of quickselect is $O(n)$" as commonly understood. Or one of its precise meanings.

the precise statement

There exists a constant $c$ such that given two integer $n$ and $k$ such that $1\le k\le n$, the average number of comparisons used in the quickselect algorithm that finds the $k$-th smallest element in an array of $n$ elements is no more than $cn$.

---

$100$ should be a good value for $c$ in general I believe, although it could possibly be as small as 4. Note that the upper bound $cn$ is independent of $k$. In other words, $k$ is not required to be fixed.

The same statement is not true if we use bubble sort instead of quickselect. We can show that bubble sort will make $\Theta(n^2)$ comparisons on average in order to find the $n/2$-th smallest element in an array of $n$ elements.

What is "the average number of comparisons"?

One might ask further what is meant exactly by that "average number". One way to interpret is to assume that every possible permutation of the given $n$ elements is equally likely to happen. For example, we can let the given array be a permutation of $1, 2, \cdots, n$, with each permutation equally likely to occur. For a permutation $\sigma$, let $\#(\sigma, k)$ be the number of comparisons used by the quickselect algorithm when the given array corresponds to $\sigma$. Then $$\text{average number of comparisons}=\frac{\sum_{\sigma\text{ is a permutation of }1,2\cdots, n} \#(\sigma,k)}{\text{number of permutations of }1,2,\cdots, n}$$

Many variations

There are many versions of the quickselect algorithm. There are other common ways to compute the average number of comparisons as well. Whichever version of the quickselect algorithm will be applied and however the average number of comparisons will be computed, that precise statement is valid in general.

Instead of on average case, for some versions of the quickselect algorithm, the number of comparisons in the worse case is no more than $c'n$ for some constant $c'$.

Exercise

Read quickselect, especially its section on time complexity, which explains the reason behind the bounds for time-complexity.