debugMinor
Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?
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.
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.
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.