Introduction

heapq.nlargest(n, iterable) is usually analyzed as O(m log n), where m is the number of input elements and n is the number of largest items you want to keep. The reason is that the algorithm can maintain a heap of size n while scanning the full iterable once.

That makes it attractive when n is much smaller than the input size. If you only need the top 10 items from a million values, building and maintaining a heap of size 10 is much cheaper than sorting all million values.

Why the Complexity Is O(m log n)

The typical strategy is:

1. read the first n items
2. build a small min-heap from them
3. for every remaining item, compare it to the heap minimum
4. if it is larger, replace the minimum and restore the heap

Heap operations on a heap of size n cost O(log n). Doing that over m input elements leads to the common bound O(m log n).

A simple sketch looks like this:

1import heapq
2
3def top_n(values, n):
4    heap = []
5
6    for value in values:
7        if len(heap) < n:
8            heapq.heappush(heap, value)
9        elif value > heap[0]:
10            heapq.heapreplace(heap, value)
11
12    return sorted(heap, reverse=True)
13
14print(top_n([3, 10, 4, 8, 1, 9], 3))

This is not the exact CPython implementation, but it shows the core idea behind the complexity analysis.

Why It Is Better Than Sorting for Small n

Sorting the full input costs O(m log m). If n is tiny relative to m, then log n is much smaller than log m, so heapq.nlargest wins asymptotically and usually practically too.

Example intuition:

• top 5 from 1,000,000 items: heap size stays 5
• full sort: all 1,000,000 items are ordered

That is the use case nlargest was designed for.

When the Advantage Shrinks

If n becomes large, especially when it approaches m, the benefit of using a heap shrinks. In that regime, a full sort can be competitive or even preferable in real implementations.

So the practical answer is:

• for small n, think O(m log n)
• for large n, behavior approaches the cost profile of sorting the whole collection

That is why people often say heapq.nlargest is ideal for "top-k" problems where k is small.

The Cost of the Final Ordering

One more detail is that the result must be returned in descending order. If the heap holds n elements at the end, ordering those final n items adds another O(n log n) step.

So a slightly fuller expression is often written as:

• scan and maintain heap: O(m log n)
• order the final result: O(n log n)

In most top-k use cases, the O(m log n) term dominates because m is much larger than n.

What About the key Argument

heapq.nlargest also supports a key function, just like sorted:

1import heapq
2
3words = ["pear", "banana", "fig", "watermelon"]
4print(heapq.nlargest(2, words, key=len))

The asymptotic picture stays the same, but the constant factors increase because each element must be evaluated against the key logic. If the key computation is expensive, it can dominate runtime regardless of the heap complexity itself.

Common Pitfalls

• Saying the complexity is always O(m log m) just because the result is ordered at the end.
• Ignoring the fact that n is the heap size, so the logarithm depends on n, not the full input size.
• Using nlargest when n is almost the entire collection, where full sorting may be just as reasonable.
• Forgetting that an expensive key function can dominate runtime even if the heap logic is efficient.

Summary

• The standard complexity answer for heapq.nlargest is O(m log n) for m input items and top n output items.
• This is much better than full sorting when n is small relative to m.
• Returning the final results in order adds O(n log n) work.
• As n approaches m, the advantage over full sorting shrinks.
• 'heapq.nlargest is best viewed as a top-k algorithm, not a general substitute for sorting everything.'