MO417- QUESTÃO PARA A PROVA ORAL
Número: 
Enunciado: Para o algoritmo: 

Fibb(n) 

1   if n <=1

2     return 1

3   else 

4     x=1

5     y=1

6     for i=2 to n

7       aux=x+y

8       y=x

9       x= aux

10   return aux    

Assinale qual é a afirmação falsa segundo o Algoritmo Fibb:

a) O algoritmo reduz um problema recursivo de O(2^n) para O(n)
b) O algoritmo requer o espaço O(n) para computar
c) O algoritmo não utiliza o método da divisão-e-conquista
d) O algoritmo consegue seu melhor caso no Θ(1)

e) NDA

Ideia original de: Sheila Katherine Venero Ferro