0

I want to implement at least two different solutions to find N-th largest element with O(N*log(N)) average time complexity in Big-O notation, where N is the number of elements in the list ?

which searching algorithm should i use in my program in java to find to n-th largest element with regards to O(N*log(N)) ?

Marsh
  • 417
  • 5
  • 19
  • you would use a quicksort, mergesort or heapsort. Please have a look at this: http://bigocheatsheet.com/ – dehlen Jan 02 '14 at 10:19

1 Answers1

2

Actually the problem you are facing can be solve in linear time using the partitioning that is part of the quick sort algorithm(Have a look here). If you really need and O(N*log(N)) algorithm than most efficient sorting algorithms will do - for instance quick sort, merge sort, heap sort.

Community
  • 1
  • 1
Ivaylo Strandjev
  • 69,226
  • 18
  • 123
  • 176
  • perfect thank you .... i do have the implementation of quick sort, merge sort, heap sort by myself. However i was hoping to understand if they are predefined in java ? – Marsh Jan 03 '14 at 09:00
  • Java's built-in sort uses `introsort` I believe. This is a mixture of several different sorting algorithms but it has a complexity of `O(N * log (N))` – Ivaylo Strandjev Jan 03 '14 at 09:01