Mostre a função de complexidade do seguinte método iterativo:
void iterativo (int n) {
int i, j, a;
a = 0;
for (i = 0; i < n; i++)
for (j = 0; j < i; j++)
a += i + j;
}
Passo 1
O método recebe um inteiro e faz um duplo laço, em que a variável vai de até e, para cada , a variável vai de até . O que queremos é contar quantas vezes a linha
é executada, pois essa é a operação básica que domina o tempo de execução. Vamos usar somatórios para expressar essa contagem.
Passo 2
Identificamos que, para cada valor fixo de , o laço interno sobre executa exatamente iterações (pois vai de até ). Logo, o número total de execuções da operação é
Passo 3
Podemos simplificar o somatório, noticing que quando i=0 ele não adiciona nada, e então começamos em i=1:
sumi=0^n-1 i ;=;sumi=1^n-1 i ;=;(n-1),n2
Passo 4
Portanto, se chamarmos de T(n) o número de vezes que a operação básica é executada, temos
T(n) = n(n-1)2
Para análise assintótica, note que
T(n) = n^2 - n2 = Theta(n^2)
Resposta
A função de complexidade exata é
T(n) = n(n-1)2,
e, em notação assintótica, o método tem complexidade Theta(n^2).