# Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity?

This is a rather well known solution to the $$k$$-th order statistic problem which requires us to find the $$k$$-th largest number in an unsorted array with $$n$$ elements where $$1 \leq k \leq n$$:

public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

for (int num: nums) {

if (heap.size() > k) {
heap.remove();
}
}

return heap.remove();
}


A brief summary of this approach is that we maintain a min heap and keep polling from this heap each time its size exceeds $$k$$. This way, our final heap will contain $$k$$ elements, and these $$k$$ elements are guaranteed to be last $$k$$ elements in the sorted array (since we have been polling minimums). Within these last $$k$$ elements, the minimum element is guaranteed to be the $$k$$-th largest so we extract the min and return that as a result.

What I don't particularly understand is why this problem is $$\mathcal{O}(n \lg{(k)})$$. For instance, after $$\mathcal{O}(n)$$ creation of the heap, we do an extraction of the minimum $$n - k$$ times, which would require sifting up in the heap $$n - k$$ times and hence, shouldn't this solution be $$\mathcal{O}(n \lg{(n - k)})$$?

Thanks!

The maximum number of elements in the heap at any given time is upper bounded by $$k+1$$.
Since each insertion or deletion from an heap requires $$O(\log \eta)$$ time where $$\eta$$ is the number of elements in the heap at the time of the operation, and $$\eta \le k+1$$, we know that each heap operation can be performed in time $$O(\log (k+1) ) = O( \log k )$$.
How many heap operations does the algorithm perform? Each element is inserted once, so there are $$n$$ insertions. In addition all but the largest $$k-1$$ elements are extracted. This yields a total of $$n + (n-(k-1)) = 2n-k+1 = O(n)$$ operations.
By multiplying the number of operations with our upper bound on the time required by each operation of $$O(\log k)$$ we obtain an overall time complexity of $$O(n \log k)$$.