Why is there no 2* in the space complexity recurrence S(n) = 2*S(n/2)?

Question

from typing import List

def recfunc(xs: List[int]) -> List[int]:
    if len(xs) < 2:
        return xs
    a = list()
    b = list()
    for x in range(len(xs)):
        if x < len(xs) // 2:
            a.insert(0, x)
        else:
            b.insert(0, x)
    return recfunc(a) + recfunc(b)

The space complexity for this function is S(n) = S(n/2) + c1*n + c2 for n>=2 where S stands for the space and c1,c2 are some constants.

Why isn't it S(n) = S(n/2)*2 + c1*n + c2?

Answer 1

In your recursive relation, S(n) represents the maximum space occupied by a function call to recfunc where n := len(xs).

Consider the line of code:

return recfunc(a) + recfunc(b)

We could have rewritten this as:

a_result = recfunc(a)
b_result = recfunc(b)
return a_result + b_result

...without changing the space requirements.

At any given time, we only need the space for at most S(max(len(a), len(b))), which is to say, at most S(n / 2). Thus:

S(n) = S(n / 2) + ...

On the other hand, if you were measuring time complexity with a recursive relation on T(n), then both of the function calls above would have occurred at some point. So we would say:

T(n) = 2 * T(n / 2) + ...