Space and time complexity of recursive implementation of summation function

Question

Can anyone advise the space and time complexity of the below code? I know that the time complexity should be O(n) because the function is called n times, and the space complexity is at least O(n) (because of stack space), but does passing a[1:] to function result in an increase in the space complexity? I think a[1:] will create a new copy of a while omitting the first element, is that right?

def sum(a):
    if len(a) == 1:
        return a[0]
    return a[0] + sum(a[1:])

Answer 1

As a recursive function, if no tail-call optimizations are applied, it will certainly have a space complexity of at least O(n) in this case, considering its execution on the memory stack. But let us analyze it further:

Time complexity

We know that sum is recursive and its stop criteria is when the input array is single length. So we know that Sum will be called at least O(n) times in the worst-case scenario, considering an input array of size n. Consider the recursion for what it is, i. e., a loop.

Inside the function, however, we have a slice operation. The slice operation l[a:b] is O(b-a), so this operation will have a complexity of O(n-1) in the first run, O(n-2) in the second run, and so on. We consider that primitively, it will perform a copy of the whole array. The overall time complexity for this function should be O(n^2) because it creates a slice per item in an array of size n.

Space complexity

Now talking about space in memory.

len(a) == 1

Here we have one copy from the return value of len(a).

return a[0]

&

    return a[0] + sum(a[1:])

In the both lines above we'll have another copy of a value that will be stored into the return address of the function. The slice also has a O(n) space complexity.

Seeing this, and considering no major-breaking optimizations are being applied by the compiler, such as a reduction, we say that the space complexity of this function is O(n) because it will make a constant number of copies for each input AND will perform a slice operation in a array of size n.

Since we said in the beginning that recursion is like a loop, considering no tail-call optimizations, this whole function will be performed n times in the worst-case scenario. The program will increase the function's memory stack until it reaches the stop criteria, until it can finally 'pop' return values from the stack of calls. The total space complexity is thus O(n*log n) as well (because every execution the input array is smaller).

Ps:

I also considered len(a) to have an O(1) time complexity, according to this.