# Finding the Kth largest element can be optimized to O(n) only if k is a constant?

There's a famous question posted on this site which asks about finding the $$k$$th largest element. Many answers are written there which optimized it and found algorithms with expectation of $$O(n)$$.

The thing I don't understand is.... Those algorithms wouldn't work if $$k$$ is dependent on $$N$$. Therefore $$k$$ must be a constant.

But if it's a constant why isn't it easiest to simply loop like bubble sort for $$k$$ times? So you pushed the $$k$$ largest elements to the end of the array. No? Complexity would be $$O(nk)$$ but $$k$$ is a const so it would be $$O(n)$$.

Why do we need crazy algorithms like median of medians and using quicksort if this alone works?

• Perfectly! Finding each Max take O(n). Then all you have to do is repeat the process k times. Since k isn't dependent on N wouldn't it be considered O of n? This looks too simple so why do people use crazy algorithms like quicksort and stuff? – bilanush Nov 6 '18 at 1:42
• The key point is exactly that $k$ may dependent on $N$. For example, how can you find the median? Here $k$ is $N/2$ or $(N+1)/2$. Those "crazy" algorithms work for that case. – Apass.Jack Nov 6 '18 at 1:53
• Mmm I thought about that. But i would think if k isn't constant but n dependant. Then.... Even using those 'crazy algorithms' wouldn't help much either. As they too would run in n squared or nlgn times. For example if you use a modified version of quicksort as suggested here en.wikipedia.org/wiki/… then... I don't see any reason it wouldn't take n squared like quicksort in worst case. So then again you haven't got any advantage compared to my simple algorithm – bilanush Nov 6 '18 at 2:23
• I am afraid you do not understand those algorithms. For one example, please check my answer to Median of medians: bound on pivot position. – Apass.Jack Nov 6 '18 at 2:30
• Ok I really do not understand them so well. I would just rely on you. Just tell me if this is correct. What you basically say is... That even if k isn't constant but grows as n grows these algorithms wouldn't take more than O(n), right? Even though quicksort itself does take a higher order – bilanush Nov 6 '18 at 2:33

The $$k$$th largest element can be found in time $$O(n)$$ for all $$k$$ using a deterministic algorithm. See Wikipedia or many textbooks, such as Cormen et al., Introduction to Algorithms.
Given the $$k$$th largest element, you can find the $$k$$ largest elements in $$O(n)$$ using a simple scan. If all elements are distinct, you just output all elements which are at least as large as the $$k$$th largest. Without this assumption, you output all elements which are strictly larger than that element, and then enough copies of the $$k$$th largest one.
• Once you've found the $k$th largest element, you can find all others in $O(n)$ by going over all elements and comparing them to the $k$th largest element. This assumes all elements are distinct; otherwise you'll have to work a tiny bit harder. – Yuval Filmus Nov 6 '18 at 1:49