il ciclo esterno viene eseguito n volte; per ogni valore di 'i', il ciclo interno è eseguito i volte, ed i varia tra 1 e n quindi il numero totale di volte che esegui il ciclo interno è pari alla somma:
1 + 2 + 3 + 4 +....+ n
ovvero è la sommatoria dei primi n numeri che vale O(n^2). Infatti puoi scrivere:
1 + 2 + 3 + ... + n =
(1 + 2 + 3 + ....+ n + 1 + 2 + 3 + ... + n) / 2 =
( (1 + n) + (2 + (n-1) + (3 + (n-2)) + ... + (n + 1)) / 2 =
n*(n+1)/2