(Questão 01-03 pontos)

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 n e faz um duplo laço, em que a variável i vai de 0 até n-1 e, para cada i, a variável j vai de 0 até i-1. O que queremos é contar quantas vezes a linha
a mathrel+= i + j
é 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 i, o laço interno sobre j executa exatamente i iterações (pois j vai de 0 até i-1). Logo, o número total de execuções da operação é
sumi=0^n-1 underbraceiiterações do laço em j çõç

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).

Exercícios relacionados