Determining time and space complexity of a recursive function

Question

def foo(n):
    def bar(n):
        if n == 0: 
            return 0
        else:
            return 1 + bar (n - 1)
    return n * bar(n)

How can I calculate what is the time complexity for the running time of foo in terms of its input n? What about space complexity?

Answer 1

Let's break it down:

 return n * bar(n)
      → n * (1 + bar(n - 1))
      → n * (1 + 1 + bar(n - 2))
      → n * (1 + 1 + 1 + bar(n - 3))
      → n * (1 + 1 + 1 + .... <n times> + bar(0))
      → n * n

This appears linear in time and memory - O(n).

Answer 2

As mentioned by cᴏʟᴅsᴘᴇᴇᴅ, It is O(n) for both runtime and space.

Let me try to explain it with a recurrence relation and derivation.

For runtime

Base case: T(0) = 1
Recurion : T(n) = T(n-1) + 1  (constant time for addition operation)


T(n) = T(n-1) + 1
     = T(n-2) + 1 + 1
     = T(n-3) + 1 + 1 + 1
     = T(n-4) + 1 + 1 + 1 + 1
     = T(n-4) + 4*1
     ...
     = T(n-n) + n * 1
     = T(0) + n * 1
     = 1 + n
     = O(n)

For space complexity

There will be 'n' stack created for all the recursive call. Hence, O(n) space.

Note: The space complexity can be further reduced with a tail recursion implementation.

Hope it helps!