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

user_12700794 0
Viewed 96
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?

space-complexity python
2 Answers

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) + ...
user_3651020

Because recfunc(b) gets executed after recfunc(a), so the same space that was used for recfunc(a) can be reused for recfunc(b). It doesn't add up like time does.

user_126710570
Related