# Problem

This function returns the result of three function calls. The function stops when the input reaches 1.

```
def f(n):
if n == 1:
return 1
return f(n - 1) + f(n - 1) + f(n - 1)
```

# Solution

The time complexity of this function is $O(3^n)$.

Each time the function is called, it branches into three separate calls. Each of these three calls will again branch into three separate calls and so on, until the base case of n = 1 is reached. The depth of the recursion tree is proportional to $n$, and each node in the tree performs $O(1)$ work, so the total time complexity is $O(3^n)$.

##### This workbook was created by Jad and Rayan Slim. Feel free to explore some of their courses:

##### The Complete Java Development Bootcamp

##### The Complete Spring Boot Development Bootcamp – Become a Java Web Developer

Feedback Summary

0.0

0 students

5

0%

4

0%

3

0%

2

0%

1

0%

Written Reviews

There are no written reviews yet.