Considere o algoritmo em pseudocódigo, descrito a seguir. para i=0 até n inicio j = 1 enquanto j<n inicio j = 2 * j para k = 0 até j inicio execute f fim fim fim Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(n 2 ).

Questão 2068119

Tecnologia da Informação · 2017

ID 2068119

Disciplina: Tecnologia da Informação

Assuntos: Complexidade de Algoritmos (Big-O, P x NP)

Ano: 2017 Banca: FGV - Fundação Getúlio Vargas Órgão: Secretaria de Estado do Planejamento, Orçamento e Gestão de Rondônia

Considere o algoritmo em pseudocódigo, descrito a seguir.

para i=0 até n

inicio

j = 1

enquanto j<n

inicio

j = 2 * j

para k = 0 até j

inicio

execute f

fim

Calcule a complexidade do algoritmo, sabendo que a função f tem complexidade igual a O(n²).