9.7.1 Algorithm 1

One can arrange the n keys into a heap and pick the k^th largest in k steps, where each step takes logarithmic time in the number of elements of the heap.

Since the construction of initial heap can be accomplished in worst case O(n)time, the worst case complexity of this algorithm is: 

O(n + klog n)

 Therefore if k$\leq$${\frac{n}{\log n}}$ or k$\geq$${\frac{n}{\log n}}$, the above algorithm will have O(n) worst case complexity.