5

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.

Jidnyasa Babar
  • 69
  • 4
  • I think it's O(nlogn). If the list has n elements, the complexity of merging one is O(logn). To merge all elements, the O is nlogn. – LeonF Aug 28 '19 at 15:30
  • I think @Jidnyasa Babar is correct, it heapq.merge is O(n) time complexity. simply try the following codes you will understand: from heapq import merge; a = [1,3,4]; b = [10,9,8]; print(list(merge(a, b))); then you will get [1, 3, 4, 10, 9, 8], merge does nothing but a selecting and "popping out" the current smallest operation from left of each array each time, it doesn't help do sorting things, so time complexity is O(K * X) K is number of array, X is average number of elements in each of the array, we can also simplify it as O(N) – Mingwei He Jan 19 '21 at 03:01

2 Answers2

3

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)

Azhar
  • 41
  • 2
1

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.

Brayoni
  • 696
  • 7
  • 14
  • wrong. simply try the following codes please: from heapq import merge; a = [1,3,4]; b = [10,9,8]; print(list(merge(a, b))); then you will get [1, 3, 4, 10, 9, 8], merge does nothing but a selecting and "popping out" the current smallest operation from left of each array each time, it doesn't help do sorting things, so time complexity is O(K * X) K is number of array, X is average number of elements in each of the array, we can also simplify it as O(N) which means this question asker is correct. – Mingwei He Jan 19 '21 at 03:02
  • @MingweiHe the question talks about merging sorted collections i.e two sorted arrays. Thus a = [1,3,4]; b = [8, 9, 10] when passed to `merge` will yield [1,3,4,8,9,10] and running time will be as I explained above. – Brayoni Feb 05 '21 at 19:12
  • how would k be different from n. shouldnt it be O(nlogn)? – Dhruv Aug 11 '21 at 03:32
  • So, finally What is the correct time complexity for heapq.merge? – Mahesh Apr 01 '22 at 20:13