algorithm – Big O Notation for a For-Loop

algorithm – Big O Notation for a For-Loop

A loop like this:

for (int i = 0; i < n; ++i) {
    doSomething(i);
}

iterates n times, so if doSomething has O(1) running time, then the loop as a whole has O(n) running time.

Similarly, a loop like this:

for (int j = 0; pow(j, 2) < n; j++) {
    doSomething(j);
}

iterates ⌈√n⌉ times, so if doSomething has O(1) running time, then the loop as a whole has O(√n) running time.

By the way, note that although pow(j, 2) is O(1) running time — so it doesnt affect your loops asymptotic complexity — its nonetheless pretty slow, because it involves logarithms and exponentiation. For most purposes, Id recommend this instead:

for (int j = 0; j * j < n; j++) {
    doSomething(j);
}

or perhaps this:

for (int j = 0; 1.0 * j * j < n; j++) {
    doSomething(j);
}

algorithm – Big O Notation for a For-Loop

Leave a Reply

Your email address will not be published.