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?

  • $\begingroup$ 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? $\endgroup$ – bilanush Nov 6 '18 at 1:42
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Nov 6 '18 at 1:53
  • $\begingroup$ 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 $\endgroup$ – bilanush Nov 6 '18 at 2:23
  • $\begingroup$ I am afraid you do not understand those algorithms. For one example, please check my answer to Median of medians: bound on pivot position. $\endgroup$ – Apass.Jack Nov 6 '18 at 2:30
  • $\begingroup$ 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 $\endgroup$ – 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.

  • $\begingroup$ Sorry I might be mixing things up. Maybe what I am actually trying to achieve is finding all k largest elements and not just the Kth one. Sorry for not being clear. I wrote it wrongly. Wouldn't it still be O of n if I go about finding largest elements . Each search for Max takes O of n and I need to iterate it k times. So I got K*n. So why do people offer much more complicated algorithms for this problem? $\endgroup$ – bilanush Nov 6 '18 at 1:40
  • $\begingroup$ Even for just finding the Kth one. I am sorry but I don't understand why does your Wikipedia page go so far with crazy algorithms? I have a much simpler one. As I noted in previous comment and in the question $\endgroup$ – bilanush Nov 6 '18 at 1:45
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 6 '18 at 1:49
  • $\begingroup$ Ok . But my algorithm is way simpler than the ones you presented... in Wikipedia. Why not use my simple algorithm? Just find k times the max $\endgroup$ – bilanush Nov 6 '18 at 2:18
  • $\begingroup$ Your algorithm takes quadratic time to find the median. Quickselect only takes linear time. $\endgroup$ – Yuval Filmus Nov 6 '18 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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