# Problem

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

```python
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](https://udemy-redirect-app.herokuapp.com/java)
##### [The Complete Spring Boot Development Bootcamp – Become a Java Web Developer](https://udemy-redirect-app.herokuapp.com/spring)





Problem 10 Solution

Problem 12 Solution

Problem 4 Solution

Problem 8 Solution

Workbook

Problem 7 Solution

Problem 15 Solution

Problem 2 Solution

Problem 14 Solution

Problem 6 Solution

Problem 5 Solution

Problem 17 Solution

Problem 3 Solution

Problem 1 Solution

Problem 16 Solution

Problem 13 Solution

Problem 11 Solution

Problem 9 Solution

Big O