The first function:
def f1(n): if n == 1: return 1 return f(f(n-1))
The second function:
def f2(n): if n == 1: return 1 return 1 + f(f(n-1))
Now I can see why both of the function’s space complexity is
O(n) since the recursion depth is equal to
But about time complexity, I’m not being able to calculate it like I used to do with the equation for normal recursion, lets say instead of
f(f(n-1)) we had
f(n-1) in the first function. then it would be
T(n) = 1 + T(n-1) = 2 + T(n-2)=... = n so
O(n), I can intuitively understand that it might stay the same for
f1, since all the returns are
1 so I might have
2n iterations which is
O(n) but I have no idea how to deal it formally.
f2 I couldn’t know how to reach the time complexity, intuition failed me here, and I would really appreciate any help in how to analyze these recursive calls.
The Final answers are:
f1: Time Complexity: O(n), Space Complexity: O(n).
f2: Time complexity: O(2^n), Space complexity: O(n).
As I think you realize, in
f1 you’re performing two operations:
f1(n - 1)
f1again with the result from the first operation.
You can see that calling
f1 with anything… or at least anything greater than zero… returns 1.
In step 2, you’re just calling
f1 again with 1, when returns immediately. O(N).
f2. Let’s examine the behavior of this function.
1 + f2(1). We know that
f2(1)returns 1, so
1 + f2(2), so 3.
So it looks like
f2(n) just returns n.
Every time we call
f2 we are doing the same things we were doing in
f1: call self with
n - 1, then call self again with whatever that number is.
In other words, we’re calling
f2 twice with
n - 1. For every n we double the number of calls, so O(2^N).