Obtenha a equação matemática referente á análise do pior e melhor caso do fragmento de código abaixo:
for(i = 0; i < N; i=i+2){
    for(j = N-i; j >=0; j--){
        if(V[i]< V[j]){
            printf("%d",i);
        }
    }
}

Passo 1

O enunciado pede pra gente analisar o custo do código em termos de N no melhor e no pior caso — basicamente é um exercício de contar iterações de loops e montar um somatório.

Passo 2

O loop externo faz i ir de 0 até menos que N, de 2 em 2. Logo, ele executa cerca de N/2 iterações. Em notação, podemos dizer que há N2 valores possíveis para i.

Passo 3

Para cada valor de i, o loop interno faz j descer de N - i até 0, inclusive. Assim, quando i vale certo valor, o número de iterações internas é
(N - i) - 0 + 1 = N - i + 1
Substituindo i pelos seus possíveis valores (0, 2, 4, …, 2 N2-1), montamos o somatório
T(N) = sumk=0^ N2 -1 (N - 2k +1)
Agora basta simplificar esse somatório:

Passo 4

Calculando o somatório
sumk=0^ N2 -1(N+1) - 2sumk=0^ N2 -1k = N2 (N+1) - 2cdot l( N2-1r) N22 = N^24 + N

Passo 5

Como as comparações do if ocorrem em todas as iterações, tanto o melhor quanto o pior caso têm o mesmo número de comparações. Se a gente contar também o printf, no pior caso ele é chamado em cada comparação atendida (ou seja, em até N^24+N vezes), mas isso só dobra o coeficiente, sem mudar a ordem.

Passo 6

Logo, em termos de notação assintótica, tanto o melhor quanto o pior caso são Theta(N^2).

Resposta

Melhor caso: Tbest(N)=sumk=0^ N2-1(N-2k+1)=N^24+N=Theta(N^2)
Pior caso: considerando também as chamadas de printf,
Tworst(N)=2l(N^24+Nr)=N^22+2N=Theta(N^2)

Exercícios relacionados