Questão
ID 1241354Disciplina: Tecnologia da Informação
Assuntos: Complexidade de Algoritmos (Big-O, P x NP)
Ano: 2021 Banca: FGV - Fundação Getúlio Vargas Órgão: Tribunal de Contas do Estado do Amazonas
Considere o pseudocódigo que define a função fibo, exibido a seguir.
function fibo(n)
if n = 1 then
return 0
elseif n = 2 then
return 1
else
penultimo ← 0
ultimo ← 1
for i ← 3 until n do
atual ← penultimo + ultimo
penultimo ← ultimo
ultimo ← atual
end for
return atual
end if
Para um inteiro n ≥ 1, a complexidade do algoritmo utilizado é: