HiveBrain v1.2.0
Get Started
← Back to all entries
debugMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
selectionfindinglargestalgorithmusingelementkthfixedonlytaking

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#110053, answer score: 2

Revisions (0)

No revisions yet.