# How to calculate time complexity of these two functions? (recursion)

#### Tags: python, recursion, time-complexity

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 `n`.
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.
For `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:

1. Call `f1(n - 1)`
2. Call `f1` again 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).

On to `f2`. Let’s examine the behavior of this function.

• When n = 1, we return `1`.
• When n = 2, we return `1 + f2(1)`. We know that `f2(1)` returns 1, so `f2(2)` returns 2.
• When n = 3, we return `1 + f2(2)`, so 3.
• Etc.

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

Source: stackoverflow