Questão 2568217

• Banca: FCC
• Órgão: TRF - 5ª REGIÃO
• Ano: 2017
• Provas: FCC - 2017 - TRF - 5ª REGIÃO - Analista Judiciário - Informática Desenvolvimento
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Considere o algoritmo abaixo.

static int fibonacci(int n) { 

   if (n <= 1) { 

      return n; 

   } 

   return fibonacci(n - 2) + fibonacci(n - 1);  

}

A complexidade deste algoritmo, na notação Big O, é  

• A. O(2ⁿ).
• B. O(n²).
• C. O(n).
• D. O(log(n)).
• E. O(n⁴).

Gabarito: A

Comentários

• Normalmente chamadas recursivas têm complexidade O(n).

  A diferença deste algorítmo é que a n, são chamadas 2 recursões, daí a resposta ser O(2ⁿ).

• Força Guerreiro!!!!!!