Si tuvieras N = 10, tus iteraciones serían: 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1. (esto es: diez iteraciones más nueve iteraciones más ocho iteraciones ... etc.).
Ahora, es necesario encontrar en la adición cuántas veces se puede obtener una N (10 en el ejemplo):
1: (10), 2 (9 + 1), 3: (8 +2), 4: (7 + 3), 5: (6 + 4). Que es 5 veces ... y descansa 5 iteraciones.
Ahora se sabe que tiene cinco decenas + 5:
10 (5) + 5
En términos de f (n) (o N), podemos ver fácilmente que esta sería la siguiente:
f (n) = n (n/2) + n/2 = (n^2)/2 + n/2 = (n^2 + n)/2 ... esta es exactamente la complejidad de estos bucle anidado.
Pero, considerando el comportamiento asintótico de Big O, podemos deshacernos de los valores menos significativos de f (n), que son el n único y el denominador.
Resultado: O (n^2)
Consulte también [Complemento de tiempo del ciclo anidado] (http://stackoverflow.com/q/526728/456814). –