Time and Space Complexity of Python list-slicing inside recursive calls

Question

Consider the below Python code that reverses a string recursively:

def reverse(s):
    if len(s) == 0:
        return s
    else
        return reverse(s[1:]) + s[0]

My thinking is that the list-slicing takes O(n-1) for both time and space in each of the O(n) recursive calls. Hence, both time and space complexities are O(n^2) (the quadratic space complexity dominates the linear recursive space needed).

Is this correct?

Answer 1

Yes, you are right.

The space complexity is O(𝑛²) because each slice allocates a new string. When the first recursive call is made, s[1:] is created, which is a string of 𝑛−1 characters. The nested recursive call will create another s[1:], which is a string of 𝑛−2 characters, ...etc.

So when arriving at the base case of recursion, strings of size 0+1+2+...+𝑛−1 lengths have been created, which represents O(𝑛²) space.

Even if you would not use slicing in the argument passed to the recursive call, but would pass an index instead, the + that is executed while unwinding the recursion will still create new strings with theses sizes, giving the quadratic space and time complexity.

The time needed to create these strings is linear to their sizes, making the time complexity also O(𝑛²).