CODEWITHSUNDEEP
pythontime-complexityheapq
Jidnyasa Babar
Jidnyasa Babar

Reputation: 79

What is the time complexity of the heapq.merge in python?

I read that the heapq.merge function is specifically used to merge 2 sorted arrays? is the time complexity O(n)? if not what is it and why? Also what is its space-complexity.

I was solving the question to merger 2 sorted arrays with 2 pointers and could achieve O(n) time complexity and O(n) space complexity.

Upvotes: 6

Views: 2130

Answers (2)

Brayoni
Brayoni

Reputation: 766

heapq.merge can be used to merge any number of sorted iterables. Its time complexity is O(NlogK) where N is the total number of elements whereas K are the items fed into the minheap for comparison.

The space complexity is O(K) because the minheap has K items at any given point in time during the execution.

Upvotes: 2

Azhar
Azhar

Reputation: 51

If you are merging K sorted arrays and each array has N elements then heapq.merge will perform the operation in time complexity of NK(logK). Because NK is the total number of elements across all the K arrays and each element has to be compared. While logK is the time complexity of the bubble down operations from the top of the heap (that is the height of the heap).

In your case K=2, log(2) = 1. So in your special case it is O(n)

Upvotes: 4

Related Questions