Big-O Komplexität für Schleifen verschachtelt

Question

Ich bin verwirrt über die Komplexität des folgenden (den Betriebes innerhalb der inneren Schleife durchgeführt wird in konstanter Zeit):

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

ist diese O (n^2) oder O (n)? Ich denke, O (n^2). Irgendwelche Ideen?

auch folgende macht mich neugierig:

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

Answer 1

Definitiv O(n squared), natürlich. Zusammenfassende Erklärung für beide Fälle: 1 + 2 + ... + n ist n(n+1)/2, das heißt (n squared plus n)/2 (und in big-O geben wir den zweiten, kleineren Teil ab, so dass wir mit n squared/2 zurückbleiben, was natürlich ist O(n squared)).

Answer 2

Sie haben Recht, diese verschachtelten Schleifen sind immer noch O (n^2). Die tatsächliche Anzahl von Operationen ist etwas in der Nähe von (n^2)/2, was nach dem Verwerfen des konstanten 1/2-Faktors O (n^2) ist.