Skip to content
Advertisement

I am curious about the time complexity

I am curious about the complexity of:-

  1. a function that multiply input by 5 (n*5)

  2. 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))

User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement