Big-O complexité pour les boucles imbriquées

Question

Je confus au sujet de la complexité des opérations suivantes (l'opération effectuée à l'intérieur de la boucle interne est en constante de temps):

for(int i=0; i<n; i++)
  for(int j=i; j<n; j++)

est la suivante O (n ^ 2) ou O (n)? Je chiffre O (n ^ 2). Toutes les idées?

aussi ce qui suit me fait curieux:

for(int i=0; i<n; i++)
   for(j=0; j<i; j++)

Answer 1

Certainement O(n squared), bien sûr. Explication sommaire pour les deux cas: 1 + 2 + ... + n est n(n+1)/2, qui est, (n squared plus n) / 2 (et grand-O nous laissons tomber la seconde, moins une partie, de sorte que nous nous retrouvons avec n au carré / 2 qui est bien sûr O(n squared)).

Answer 2

Vous avez raison, ces boucles imbriquées sont toujours O (n ^ 2). Le nombre réel d'opérations est quelque chose proche de (n ^ 2) / 2, qui, après avoir éliminé le facteur constant 1/2, est O (n ^ 2).