Big O
)}

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

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