GabaritoA — O(2ⁿ).
Gabarito: letra A. O algoritmo recursivo de Fibonacci apresentado possui complexidade exponencial O(2ⁿ) porque cada chamada gera duas novas chamadas recursivas, formando uma árvore binária de altura n, com aproximadamente 2ⁿ chamadas totais (ignorando constantes).
A banca cobra a análise da recursão em árvore binária. O erro típico é confundir a profundidade da recursão (n) com o número total de chamadas, que cresce exponencialmente. Cada ramificação dobra o trabalho a cada nível.
O número de chamadas recursivas segue aproximadamente a sequência de Fibonacci, cujo crescimento é exponencial. Na notação Big O, a cota superior é O(2ⁿ), pois cada nó pai gera dois filhos até a profundidade n.
O(2ⁿ) é exponencial, não quadrático. Complexidade O(n²) aparece em algoritmos com dois loops aninhados sobre a entrada, não nesta recursão.
O(n) seria linear, como um único loop. A recursão do Fibonacci gera muito mais chamadas: cada nível dobra a quantidade.
O(log n) é típico de algoritmos que dividem o problema pela metade a cada passo (ex.: busca binária). Aqui o problema não é reduzido pela metade, mas sim dividido em dois subproblemas de tamanho n-1 e n-2, gerando explosão combinatória.
O(n⁴) é polinomial de grau 4. A recursão do Fibonacci tem crescimento exponencial, muito mais rápido que qualquer polinômio.
O candidato pode achar que a complexidade é O(n) porque a profundidade máxima da recursão é n. No entanto, a cada nível o número de chamadas dobra, resultando em 2ⁿ chamadas totais – uma armadilha clássica de análise de recursão em árvore.
Gabarito: letra A.
Link permanente: /questoes/fc038598