CODEWITHSUNDEEP
ctime-complexitycomplexity-theory
w.kovacs
w.kovacs

Reputation: 49

Time complexity of loop

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

Upvotes: 3

Views: 188

Answers (3)

Yacoub Massad
Yacoub Massad

Reputation: 27861

It is O(n), because the loop will iterate exactly n times.

On interation 1: the value of i would be 1 * 1 - 1 which is 0

On interation 2: the value of i would be 2 * 2 - 1 which is 3

On interation 3: the value of i would be 3 * 3 - 1 which is 8

...

On interation n: the value of i would be n * n - 1. This causes the loop to terminate.

In summary, i grows fast enough to reach n * n - 1 in n iterations.

Upvotes: 1

Haris
Haris

Reputation: 12270

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)

Upvotes: 3

Servy
Servy

Reputation: 203824

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).

Upvotes: 6

Related Questions