Determine a complexidade do algoritmo abaixo: Função teste ( n ); A=1; B=1000; Enquanto B > A faça para i=1 até n faça A = A * log2(i); escreva( A ); fim_para; fim_enquanto; fim.

Análise da Complexidade do Algoritmo

Vamos analisar passo a passo o algoritmo apresentado:

Estrutura do Código

Comportamento das Variáveis

1. Inicialização: A = 1, B = 1000
2. Condição do While: B > A significa que o laço continua enquanto A < 1000
3. Crescimento de A: Em cada iteração do for, A é multiplicado por log₂(i)

• Isso faz com que A cresça exponencialmente (multiplicativamente)
• Para atingir o valor 1000, são necessárias poucas iterações externas

1. Número de Iterações Externas: Como A cresce exponencialmente, o número de vezes que o while executa é O(log n)
2. Número de Iterações Internas: O for sempre executa exatamente n vezes

Cálculo da Complexidade Total

Consideração Importante

Nota: Existe um detalhe técnico no código original onde log₂(1) = 0, o que tornaria A = 0 na primeira iteração e criaria um loop infinito. No entanto, em questões de concursos, geralmente considera-se o caso teórico válido para análise de complexidade.

Resumo

Alternativa D

O algoritmo tem complexidade O(n log n) porque:

• O laço interno (for) executa n vezes em cada passagem
• O laço externo (while) executa O(log n) vezes devido ao crescimento exponencial de A
• Multiplicando ambos: O(n) × O(log n) = O(n log n)