Suppose we have the following functions:
def merge_sort(items):
if len(items) <= 1:
return items
middle_index = len(items) // 2
left_split = items[:middle_index]
right_split = items[middle_index:]
left_sorted = merge_sort(left_split)
right_sorted = merge_sort(right_split)
return merge(left_sorted, right_sorted)
def merge(left, right):
result = []
while (left and right):
if left[0] < right[0]:
result.append(left[0])
left.pop(0)
else:
result.append(right[0])
right.pop(0)
if left:
result += left
if right:
result += right
return result
For the last few weeks, I have been learning about space and time complexity. In particular, I am struggling with understanding how to calculate the space complexity of recursive functions. Can someone give me a detailed explanation of the space complexity of this merge sort function? In general, how do we calculate the space complexity of recursive functions? It would be greatly appreciated if you could help answer these two questions!
