3 ms·
They are probably thinking of simply going through the list and tracking the top 3. This gives you linear time but as you noted you can go faster with quicksele
by smiths1999 6y ago
They are probably thinking of simply going through the list and tracking the top 3. This gives you linear time but as you noted you can go faster with quickselect (edit: I originally mistakenly wrote selection sort despite thinking of quickselect), giving you linear time (edit: I original said logarithmic time, which is obviously wrong).
I suppose it is besides the point, but you shouldn't be reaching for a specific algorithm but rather using your language's library sort algorithm.
- andi999 6y agoWhat do you nean with selection sort giving logarithmic time? I mean any algorithm finding anything unique on an unsorted list has to be at least O(n) or resort to magic.
- smiths1999 6y agoWell I was actually thinking of quickselect, but regardless I was too quick to post. Quickselect is O(n) average time (as you pointed out).