I can sort a list of n items in O(n log n) with quicksort or heapsort easily. I've been challenged that there is a way to get the top Log n elements in O(n). Do you have any idea about how this can be accomplished?

Printable View

- 12-05-2010, 04:19 AMmerikSorting challenge
I can sort a list of n items in O(n log n) with quicksort or heapsort easily. I've been challenged that there is a way to get the top Log n elements in O(n). Do you have any idea about how this can be accomplished?

- 12-05-2010, 06:22 PMcouling
I'm inclined to believe this is impossible. You must touch at least all n elements once, but you want to keep hold of an expanding number of them (log n). The fact that the number you want to select increases as n increases means you need to add an extra term.

If you were selecting a fixed constant of rows (eg: top 10) then the complexity could be O(n).

The best I can come up with appears to have a complexity of O( n log ( log ( n ) ):

- Prime a priority queue with the first log ( n ) elements:
- For each of the remaining elements:
- Add the element to the priority queue
- Remove the smallest element from the priority queue

- Whatever is left in the priority queue at the end will be the top log(n) elements

Interestingly you can combine the add and remove operations together for speed, that is to add one and remove one together:- Compare the item to be added with the next to be removed. If the one to be added is smaller then stop.
- Replace the one to be removed with the one to be added.
- while the added value is larger than one of the values above it: Bubble up the added value (as you would for an empty space in the normal remove algorithm)

This would give it a best case of O(n), but the worst case would still be O( n log ( log ( n ) ). - 12-05-2010, 07:12 PMmerik
Thank you for your great answer. It was very enlightening.