Algorithm Complexity

[Gast]

Hallo allerseits, hoffe einer kann mir auf die schnelle helfen, schreibe morgen eine Klausur und bin noch nicht ganz damit vertraut...

geg.:
sum = 0;
for (i = 0; i < n; i=i+2) {
for (j = 0; j < n * n; j++) {
sum++;
}
}


Meine Lösung = O(N³), könnte das so hinkommen? einmal das N^1 von der ersten Schleife und das N² ( n * n ) von der zweiten...N ^ 1 + N ^ 2 = N ^3?

[Der_Korken]

Sollte O(n³) sein, ja. Du hast aber unten geschrieben: n³ = n + n². Das stimmt natürlich nicht. Bei verschachtelten Schleifen musst du die Anzahl der Durchläufe jeweils multiplizieren, also (n/2)*n² = n³/2 = O(n³). Ständen die Schleifen hintereinander, dann wäre es (n/2)+n², was aber dann nicht O(n³) wäre, sondern O(n²).