Considere um algoritmo composto por comandos primitivos e dois loops aninhados com contadores independentes. O loop mais externo tem M repetições enquanto que o loop interno tem N repetições. O que podemos afirmar sobre o tempo do algoritmo? Qual seria o seu tempo se os loops fossem invertidos (loop mais interno se tornasse o mais externo e vice-versa)?
Passo 1
O enunciado apresenta um algoritmo formado por comandos primitivos e dois loops aninhados cujos contadores são independentes. O loop externo repete
vezes e, para cada iteração dele, o loop interno repete
vezes. O conteúdo da matéria é análise de complexidade de tempo em algoritmos.
Passo 2
Para estimar o tempo total, note que o corpo do loop interno será executado exatamente uma vez para cada par
com
e
. Se cada execução do corpo custa tempo constante
, então
Em notação assintótica isso dá
Passo 3
Se invertermos a ordem dos loops — isto é, o loop que antes era interno (com
repetições) passa a ser externo, e vice-versa — a contagem de execuções do corpo continua sendo todos os pares
com
,
. Logo, ainda temos
Resposta
O tempo do algoritmo é
e permanece
mesmo se os loops forem invertidos.