# 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).

- For building the heap for first t elements will be done
`tlog(t)`

- For pushing and popping, the remaining elements will be done in

`(n-t)log(t)`

- The overall time complexity will be
`nlog(t)`

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

Its actually O(n+t*log(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 t*log(n). Therefore time complexity will be O(n+t*log(n))