How is the space complexity O(m+n) here?

Question

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

I know it has something to do with the stack. Can someone make this clear for me? I'm new to this thanks.

Answer 1

The fundamental thing about the algorithm is that each recursive call is picking one element off either l1 or l2. Since that can only happen M + N times, the time complexity is going to be O(M + N).

The space complexity is another matter.

I know it has something to do with the stack.

Yes. In Python, recursive calls require a stack frame for each level of recursion. The stack frame holds the call arguments and local variables, and the information needed to allow the call return to the correct place in the code that called it.

In your example, there are M + N levels so the space complexity of the stack space is O(M + N).

Assuming that your linked list nodes are implemented in an obvious fashion, your merge method is mutating the l1 and l2 objects, and is not consuming any more space.

---

Many languages / compilers support something called tail call optimization for many cases where a method that recursively calls itself. When possible, the recursive call is optimized to a jump to the start of the method rather than using a call instruction. Thus a stack frame is not required.

In your example, the space complexity for stack usage would be O(1).

However Python does not support this; see Does Python optimize tail recursion?