Zeit Komplexität von zwei verschachtelten Schleifen

Question

Ich studiere Algorithmen und ich habe ein Problem, das ich nicht lösen kann.

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

So, Zeit Komplexität dieses Codes ist n^2. Aber. Die erste Schleife wiederholt sich n-mal und das verstehe ich. Aber die zweite Iteration ist n (n + 1)/2. Also .. Es wird n * (n (n + 1))/2. Wo bin ich falsch gelaufen?

Answer 1

Zunächst müssen Sie die Big-O-Notation verstehen. Es wirft alle Terme niedrigerer Ordnung ab und behält nur die höchste N.

Ihre äußere Schleife läuft N mal, so ist der höchste Begriff n und was ist der höchste value für innere Schleife? Es ist (n-1).

Also für Nth Iteration der äußeren Schleife, erhalten Sie n-1 Iteration für die innere Schleife, die N(N-1) = (N^2 - N) und mit Big-O ist es O(N^2)