Calcule a complexidade, no pior caso, do fragmento de código abaixo:
int i,j,s;
s = 0;
for(i=1; i < N-1; i++)
for(j=1; j < 2*N; j++)
s = s + 1;
int i,j,s;
s = 0;
for(i=1; i < N-1; i++)
for(j=1; j < 2*N; j++)
s = s + 1;
Passo 1
O enunciado nos dá um trecho de código em C com dois loops aninhados e pede a complexidade de tempo no pior caso. O conteúdo que vai rolar aqui é contagem de iterações em loops aninhados para descobrir como a quantidade de operações cresce com N.
Passo 2
Primeiro, vamos analisar o laço interno. Ele é: for(j=1; j < 2N; j++) s = s + 1;. O contador j vai de 1 até 2N–1, ou seja, faz exatamente (2N–1) iterações. Em termos de ordem de grandeza, isso é
(N) porque 2N–1 cresce linearmente em N.
Passo 3
Agora, o laço externo é: for(i=1; i < N-1; i++). Aqui i vai de 1 até N–2, totalizando (N–2) iterações, que também é
(N).
Passo 4
Como os loops são aninhados, a instrução s = s + 1 é executada (N–2)·(2N–1) vezes. Multiplicando e focando no termo dominante:
2N^2 – 5N + 2
2N^2 – 5N + 2
N^2
Passo 5
Logo, a complexidade de tempo no pior caso, em notação assintótica, é
O(N^2)
O(N^2)
Resposta
O(N^2)