algorithmrecursionbig-otime-complexityspace-complexity# How do you find the space complexity of recursive functions such as this one?

```
f (int n){
if (n<=0){
return 1;
}
return f(n-1) + f(n-1);
}
```

Suppose we did f(4). My thought was that it would be O(2^n), since then in order to find f(n-1) + f(n-1) we would have to push f(n-1) = f(3) to the call stack twice, and then f(2) four times the call stack, etc. However, the book I got this from says that is is O(n). Why is that true?

Solution

Let's imagine evaluating this for f(4) (the example you consider). Here's how it would go. The stack starts by looking like

```
I need to compute f(4)
```

Then the calculation of f(4) recurs to `f(3), and the stack looks like

```
I need to compute f(4), so
I need to compute f(3)
```

Then we keep going down and we eventually get to

```
I need to compute f(4), so
I need to compute f(3), so
I need to compute f(2), so
I need to compute f(1), so
I need to compute f(0)
```

Then, we can calculate f(0) as 1, and the last call returns. The penultimate call (the one to compute f(1)), then wants to compute the second copy of f(0), and the stack goes to:

```
I need to compute f(4), so
I need to compute f(3), so
I need to compute f(2), so
I need to compute f(1), and although I've already computed the first f(0)=1, I still need to compute the second occurrence of f(0), so
I need to compute f(0) (again)
```

Then that returns, and so the computation of f(1) can return, and we get to

```
I need to compute f(4), so
I need to compute f(3), so
I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0)
```

and from there the stack becomes:

```
I need to compute f(4), so
I need to compute f(3), so
I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0), so...
I need to compute f(1)
```

and it will continue computing f(1) as before.

The point is that the stack only ever gets as deep as n, even though (ultimately) 2^n operations will be performed. So the time complexity is O(2^n) but the space complexity is only O(n).

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array