Finding the $k$th largest element in an unsorted array What is the complexity of finding the k'th largest element in an unsorted linked list? If we sort the list, I think that the complexity is O(nlogn + k)=O(nlogn) since k &lt; n. Is there a way of finding the kth largest element without sorting the list?
Yes, there is. Selection algorithm. There are two versions: running in worst-case linear time, and in expected linear time (see Cormen's chapter 9).
You can also implement this algorithm to run in sublinear time using data structures.