Degree of complexity

Asked

Viewed 39 times

1

def fRecursivo(n):
    if(n == 0 ):
        return 1
    if (n%2 ==1):
        return (n+3*fRecursivo(n-1))
    if(n%2 == 0 and n> 0):
        return (n+n+3*n*fRecursivo(n-1))

How complex is the code for even numbers ? In the case when the line is called:

return (n+n+3*n*fRecursivo(n-1))
python algorithm

1 answer

2

If n is even and greater than zero, the recursive call to n - 1, which is unique and therefore falls in the second if.

There is another recursive call to n - 1, which is even (may or may not be greater than zero).

That is, for any n greater than zero are made n recursive calls, until zero.

So the complexity is O(n).

Browser other questions tagged python algorithm

You are not signed in. Login or sign up in order to post.