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

Qual o grau de complexidade do código para os números pares ? No caso quando for chamado a linha:

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

1 Resposta 1

2

Se n é par e maior que zero, é feita a chamada recursiva para n - 1, que é ímpar e portanto cai no segundo if.

Ali é feita outra chamada recursiva para n - 1, que é par (podendo ou não ser maior que zero).

Ou seja, para qualquer n maior que zero são feitas n chamadas recursivas, até que se chegue a zero.

Portanto a complexidade é O(n).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .