Considere a seguinte função recursiva c… (Fundatec 2025)

InformáticaLógica de programação e algoritmosFundatec 2025

SBC

Considere a seguinte função recursiva calcula_algo(n): def calcula_algo(n): if n <= 1: return 1 else: return calcula_algo(n - 1) + calcula_algo(n - 2) Sobre a complexidade de tempo T(N) e complexidade de espaço S(N) dessa implementação recursiva, é correto afirmar que:

AT(N)=O(N) e S(N)=O(logN), devido à otimização de compilação.BT(N)=O(2N) e S(N)=O(N), devido à exponencial duplicação de chamadas e à profundidade da pilha de chamadas.CT(N)=O(N2) e S(N)=O(N), porque cada chamada recursiva adiciona uma entrada à pilha.DT(N)=O(NlogN) e S(N)=O(1), pois a maioria das chamadas são memorizadas implicitamente.ET(N)=O(logN) e S(N)=O(N), assumindo que o sistema operacional gerencia a pilha de forma otimizada.

Mais questões de Lógica de programação e algoritmos

Ver as 2.108 questões de Lógica de programação e algoritmos

Questão de prova oficial, com o gabarito definitivo publicado pela banca. Reproduzida para fins de estudo.