Virag Dhulia wrote: > What could be the most efficient algo for finding the Nth highst element in > an M-Element list where N<M always??
Are the elements in an array already, or are you reading them in? If they're already in an array, you can do it in O(M) time using a linear-time selection algorithm. Randomized quickselect runs in O(M) expected time. If you're reading them in, you don't even need to store all M elements. It's straightforward to do it in O(M log N) time and O(N) space using a heap. It's also possible to do it in O(M) time and O(N) space using a linear-time selection algorithm. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
