Considere o código-fonte que segue:int f1(int n) {     if (n...

Alternativa correta: C - O(2ⁿ) e O(n)

Vamos entender por que essa é a alternativa correta e analisar as alternativas incorretas.

Função f1(n)

A função f1(int n) é uma função recursiva que define uma relação de recorrência. A análise do tempo de execução de uma função recursiva depende de quantas vezes a função é chamada recursivamente.

O código da função é o seguinte:

int f1(int n) {
if (n == 0 || n == 1) return n;
else return (2 * f1(n-1) + 3 * f1(n-2)); }

A função f1 chama a si mesma duas vezes para calcular f1(n-1) e f1(n-2). Isso implica que a profundidade da recursão cresce exponencialmente com n. Portanto, a complexidade de tempo para f1(n) é O(2ⁿ), pois o número de chamadas recursivas cresce exponencialmente.

Função f2(n)

A função f2(int n) utiliza laços para calcular seu resultado em vez de recursão. O código relevante é:

int f2(int n) {
int a; int[] X = new int [n];
int[] X = new int [n]; int[] Z = new int [n];
X [0] = Y [0] = Z [0] = 0;
X [1] = 1; Y [1] = 2; Z [1] = 3;
for (a = 2; a <= n; a++) {
X [a] = Y [a-1] + Z [a-2];
Y [a] = 2 * X [a]; Z [a] = 3 * X [a]; }
return X [n]; }

O laço for executa n-1 iterações (de 2 até n). Dentro do laço, as operações executadas têm complexidade constante O(1). Portanto, a complexidade do tempo de execução para f2(n) é O(n), pois o laço domina a complexidade e executa linearmente em relação a n.

Análise das Alternativas

A - O(2ⁿ) e O(2ⁿ): Incorreta. A função f2(n) tem complexidade O(n), não O(2n).

B - O(n) e O(2ⁿ): Incorreta. A função f1(n) tem complexidade O(2n), não O(n).

D - O(n) e O(n): Incorreta. A função f1(n) tem complexidade O(2n), não O(n).

E - O(n) e O(log n): Incorreta. A função f1(n) tem complexidade O(2n), e a função f2(n) tem complexidade O(n), não O(log n).

Portanto, a alternativa C - O(2ⁿ) e O(n) é a resposta correta, pois reflete corretamente a complexidade de tempo das funções f1(n) e f2(n).

F1 temos fibonacci recursivo, que tem complexidade O(2n).

F2 temos fibonacci não recursivo, que tem complexidade O(n).

Esse é um assunto que não tenho domínio, então se alguém tiver algo a acrescentar ou mesmo retificar, eu agradeceria.

Força Guerreiro!!!!!!

Nem ferrando que fibonacci recursivo é 2n...

Deveria ser 2^n

@Leandro Henrique concordo contigo. Imagino que seja 2 elevado a N, porém, na hora de pega a questão perderam esse detalhe.

Pensei o mesmo que o Leandro, acabei fazendo por eliminação. Pode ter sido na transcrição da questão