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

Leave a Reply

Your email address will not be published.