Time complexity of loop

Question

I'm unsure as to the complexity of the following block of C:

int i = 0, j = 1;
for ( i = 0; i < n * n; i += j )
{
    O1();
    j += 2;
}

where O1 is a function that obviously takes constant time to execute. Now, I am aware that loops whose counter gets increased by a constant amount every iteration generally have a complexity of O(sqrt(n)), but is this the case here as well? Or is it O(sqrt(n^2)), that is O(n)?

Thanks

Answer 1

I am aware that loops whose counter gets increased by a constant amount every iteration generally have a complexity of O(sqrt(n))

That's false. A loop whose counter gets increased by a constant amount every iteration is O(N).

A loop whose counter increases by an amount that increases linearly on each iteration is O(sqrt(N)).

In this case, N here is n * n, as that's what your loop is looping until, so that simple replacement tells you that, yes, the operation is O(sqrt(n^2)) or O(n).

Answer 2

I am aware that loops whose counter gets increased by a constant amount every iteration generally have a complexity of O(sqrt(n))

Nope! That is not true. Take for instance this loop

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

Its variable i is increasing by constant amount, i.e 1. But the complexity of this loop is O(n)

---

If you see the series closely, the values i will get are

0, 3, 8, 15, 24, 35, ...

Its an arithmetic series. It can also be written as

0^2 - 1, 1^2 - 1, 2^2 - 1, 3^2 - 1, 4^2 - 1, 5^2 - 1, 6^2 - 1, ...

---

Now the loop will run until i reaches n^2, (i < n*n)

So you can deduce from that, that the loop will run for O(n).

Therefore the complexity is O(n)