The following code has average running time to be O(n). One can improve it to O(n) in worst case time by a median of median scheme of finding pivot. <br/><br/>The key idea is similar to quick sort. One choose a pivot (x) and partition the list into two groups(one group >=x, the other group < x). Then ,one searches in the group that contain the kth largest entry or return the pivot if the pivot is the entry to find. This will have average complexity of O(n) but one can further improve it by finding a pivot that well partition the list and this is called the median of median method in the literature.