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

Question

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.

Answer 1

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)