Time and space complexity of this function

def f3(n):
   if n <= 1:
      return 1
   L = [i for i in range(n)]
   return 2 * f3(n // 2) + 1

I am trying to calculate the time and space complexity of this function, and I have a very important question about the last part 2*f3(n//2): do we consider it 2 recursive calls, or is it just one?

Here's how I'm calculating: T(n)=n+2T(n//2)=n+2*[n/2 + 2t(n//4)]=2n+4T(n//4)=...=kn + 2^k*T(n/(2^k)) which stops at whenever n/(2^k) = 1 then n = 2^k, log(n)=k. So we have log(n) iterations, by substituting back we get nlog(n)+n*1 which means time complexity of O(nlog(n)), and same for space complexity since we're using list comprehension.

But now looking at it again 2*f3(n//2), is it the same as f3(n//2)+f3(n//2), or I'm making a big mistake?

Because if it's only one call to the function the time and space complexity will be O(log(n)), I guess.

I would appreciate any explanation about my question, and would be happy to hear any feedback and tips about my answers.

Solution

The number of recursive calls is O(lg n), but you still need to take into account how much work each of those calls does. That work (computing L) is linear in the size of the input. As a result, the total time complexity is essentially the sum n + n//2 + n//4 + ... + 1, which you should be able to verify as O(n).

The space complexity depends on what exactly you need to do with L. You can reduce the space complexity by getting rid of it before the recursive call if you don't need it during or after the recursive call.