Time Space Complexity of Recursive Functions

Question

This is from a leetcode problem here: https://leetcode.com/problems/reverse-string/solution/

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example:

Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Solution 1:

class Solution:
    def reverseString(self, s):
        def helper(left, right):
            if left < right:
                s[left], s[right] = s[right], s[left]
                helper(left + 1, right - 1)

        helper(0, len(s) - 1)

Time complexity : O(N) time to perform N/2 swaps. Space complexity : O(N) to keep the recursion stack.

Solution2:

class Solution:
    def reverseString(self, s):
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left, right = left + 1, right - 1

Time complexity: O(N) to swap N/2 element. Space complexity: O(1), it's a constant space solution.

Can someone please explain why the space complexity in solution 2 is O(1) while the space complexity in solution 1 is O(n)?

Is it because solution 1 requires a function call?

Thanks in advance!

Answer 1

When you call a function recursively, behind the scenes a new stack frame is created to hold the return address and variables you create in the new call.

Each recursive call does this, so if a function calls itself n/2 times, that's O(n) storage space.