Calcule a complexidade, no pior caso, do fragmento de código abaixo:
int i,j,k,s;
for(i=0; i < N-1; i ++)
    for(j=i +1; j < N; j++)
        for(k=1; k < j; k++)
            s = 1;

Passo 1

O enunciado pede pra calcular, no pior caso, a complexidade de tempo de um trecho em C que tem três loops aninhados. O conteúdo da matéria é análise de algoritmos, em particular conversão de loops em somatórios e uso de fórmulas de séries aritméticas para encontrar a ordem de crescimento.

Passo 2

Pra contar quantas vezes o corpo (a atribuição de s) é executado, a gente escreve um somatório triplo que reflete cada loop em i, j e k. Assim temos:
T(N)=sumi=0^N-2sumj=i+1^N-1sumk=1^j-11

Passo 3

O próximo passo é simplificar o somatório sobre k, pois para cada par (i,j) o loop em k faz exatamente j−1 iterações. Logo:
sumk=1^j-11 = j-1
E portanto
T(N)=sumi=0^N-2sumj=i+1^N-1(j-1)

Passo 4

Agora a gente calcula o somatório interno em j usando soma de termos de progressão aritmética. Primeiro separamos:
sumj=i+1^N-1(j-1)=sumj=i+1^N-1j - sumj=i+1^N-11
Pelo fórmula da soma de 1 até M temos sumj=1^Mj=M(M+1)2. Aplicando de j= i+1 até N-1 e simplificando, obtém-se uma expressão polinomial em N e i de grau 2.

Passo 5

Finalmente, ao somar essa expressão sobre i de 0 até N−2, a gente gera um polinômio de grau 3 em N. O termo de maior ordem vem de integrar j sobre i e j, resultando em uma constante vezes N^3. Logo a complexidade, no seu termo dominante, cresce como N^3.

Resposta

O(N^3)

Exercícios relacionados