# python – What is the time complexity of heapq.nlargest?

## python – What is the time complexity of heapq.nlargest?

The speaker is wrong in this case. The actual cost is `O(n * log(t))`. Heapify is called only on the first `t` elements of the iterable. Thats `O(t)`, but is insignificant if `t` is much smaller than `n`. Then all the remaining elements are added to this little heap via `heappushpop`, one at a time. That takes `O(log(t))` time per invocation of `heappushpop`. The length of the heap remains `t` throughout. At the very end, the heap is sorted, which costs `O(t * log(t))`, but thats also insignificant if `t` is much smaller than `n`.

## Fun with Theory 😉

There are reasonably easy ways to find the tth-largest element in expected `O(n)` time; for example, see here. There are harder ways to do it in worst-case `O(n)` time. Then, in another pass over the input, you could output the `t` elements >= the t-th largest (with tedious complications in case of duplicates). So the whole job can be done in `O(n)` time.

But those ways require `O(n)` memory too. Python doesnt use them. An advantage of whats actually implemented is that the worst-case extra memory burden is `O(t)`, and that can be very significant when the input is, for example, a generator producing a great many values.

For Heapq t largest or t smallest, the time complexity will be `O(nlog(t))`

Heapq will build the heap for the first t elements, then later on it will iterate over the remaining elements by pushing and popping the elements from the heap (maintaining the t elements in the heap).

1. For building the heap for first t elements will be done `tlog(t)`
2. For pushing and popping, the remaining elements will be done in
`(n-t)log(t)`
3. The overall time complexity will be `nlog(t)`

#### python – What is the time complexity of heapq.nlargest?

Its actually O(n+tlog(n)) because heapify takes O(n) and for every element of largest or smallest takes O(log(n)). So for t largest/smallest it takes tlog(n). Therefore time complexity will be O(n+t*log(n))