CODEWITHSUNDEEP
pythonsorting
Alexandru Oporanu
Alexandru Oporanu

Reputation: 13

Space complexity for mergesort

It is unclear for me if this snippet of merge sort has space complexity of O(n log n) or O(n).

def mergeSort(L): 
    N = len(L)
    
    if N <= 1:
        return L
    
    mid = N // 2
    L1 = mergeSort(L[: mid])
    L2 = mergeSort(L[mid :])
    return merge(L1, L2)

Assuming that merge(L1, L2) uses auxiliar memory of O(len(L)) (i.e O(n)), doesn't every level of the recursion tree use O(n) auxiliary memory. And as long the tree has like O(log n) levels wouldn't it be O(n log n) ? A lot of sources on the internet use the exact same implementation and they say that the space complexity is O(n), and I do not understand why?

Upvotes: 1

Views: 105

Answers (2)

Tim Peters
Tim Peters

Reputation: 70602

The space complexity is O(N), which is not just expected case, but also best and worst case. While O(log(N)) levels of recursion may be active, a merge can be in progress only on the current level, and is not itself recursive. When the memory for the merge is done, it's released - it doesn't remain in use. All merges can (re)use the same chunk of N locations.

Upvotes: 1

Chinmay Naik
Chinmay Naik

Reputation: 58

The time complexity is O(nlog(n))

Upvotes: 0

Related Questions