Big O Notation for a For-Loop

Question

How do I find the Big O Notation for this for-loop line of code

for (int j = 0; pow(j,2) < n; j++) ?

Does anyone know?

I have read a little on Big O Notation and it’s a very confusing topic to understand. I know that usually for-loop like this one → for (int n = 0; n < 20; ++n), have a Big O notation of O(1), as input increases by 13 so does its output, with linear complexity. Is that the same situation as above?

Answer 1

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 doesn't affect your loop's asymptotic complexity — it's nonetheless pretty slow, because it involves logarithms and exponentiation. For most purposes, I'd 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);
}