Para cada loop em lote, costumamos assumir um fator na notação assintótica e é claro que o impulso nos leva a crer que casos como esse são O(n*n)=O(n²)
, como se cada loop aplicasse um fator linear, mas há vezes que não é assim.
Por exemplo, aplicar o quicksort em loops (e não recursões) resulta num comportamento predominantemente O(n*log(n))
, mesmo podendo implementar com dois loops e no pior caso sendo O(n²)
. Mais ainda, o mergesort em loops bem implementado sempre é O(n*log(n))
, quer seja com dois loops em lote, quer seja com três. Sendo assim, vamos analisar.
No loop de i
, encontramos que ele executa 1x se n=1
ou n=2
, 2x se n=3
ou n=4
, daí em diante linearmente, pois caminha de duas em duas unidades por ciclo até uma fixa condição de parada. Se n<=0
, executa 0x. Quer dizer, o número de ciclos do loop de i
é max(0,ceil(n/2))
, para simplificar é entendido como n/2
.
Já no loop de j
, o número de vezes que executa é simplesmente (n-i)x, pois na primeira ele executa 0x, na segunda, 2x, na terceira, 4x e daí em diante, até o fim dos loops em 'i' que reduzem esse índice de dois em dois. O número de ciclos em j
é n-i
.
Sendo assim, a série é n+(n-2)+(n-4)+...+3+1
(se n
for ímpar) ou n+(n-2)+(n-4)+...+4+2
(se n
for par). Isso resulta nas duas fórmulas:

quando n
é par ou

quando n
é ímpar.
Ambos resultam na mesma fórmula assintótica, que é a da complexidade do algoritmo: O(n²)
.