I am curious about the complexity of:-
a function that multiply input by 5 (n*5)
a function that add 5 to the input (n+5)
def func(n): if n <= 0: return 1 return func(n-1) + func(n-2) + func(n-3)
in (3) is the time complexity o(3**n)?
Advertisement
Answer
Strangely enough, O(func(n))
is just func(n)
. Why? The only real think your code can do is add 1. So whatever result it go, it got there by calling itself some multiple of func(n)
times.
The same logic applies to the Fibonacii function. The naive implementation has time O(fib(n))