Computational Complexity

[sawer]

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

Is complexity for this loop O(1) or O(n)?

[GCDEF]

O(n) as it would vary linearly with the number of times the loop is executed.

[Zachm]

Actually, if the upper limit is constant (100), and will remain a constant, then it is O(1).
Algorithm with run-time complexity of O(n) merely implies that the run-time of the algorithm exhibits linear growth with relation to the size of the input.
Your code has no input and each time you run it, it will execute exactly 100 iterations - which means that no matter what input you will give the algorithm, the run-time is constant - 100 iterations, hence it's run-time complexity is O(1).

A smart compiler will not even translate this loop into machine code since the for loop is empty.

Regards,
Zachm

[Peter_APIIT]

Why someone say this is O(1) and O(n) ?

I believe that analysis of this algorithm run in o(n).

[laserlight]

Why someone say this is O(1) and O(n) ?

That "someone" is not the same since GCDEF says that it is in O(n) but Zachm says that it is in O(1).

I believe that analysis of this algorithm run in o(n).

I disagree as Zachm's analysis looks correct to me. If the complexity of this algorithm is in O(n), then what is n?

EDIT:
That said, if an algorithm's complexity is in O(1) then it is also in O(n), but I presume that we are abusing big-O notation here as it is often abused to mean theta (or something like that, I have not taken my algorithms module in university yet, so I can claim ignorance ).

[Mybowlcut]

I did algorithm complexity this semester at uni and as Zachm said, that is O(1) since it has no input, ie. will always be run 100 times.

[Zachm]

That said, if an algorithm's complexity is in O(1) then it is also in O(n), but I presume that we are abusing big-O notation here as it is often abused to mean theta (or something like that, I have not taken my algorithms module in university yet, so I can claim ignorance ).

You don't need to claim ignorance , the following is always true:

if f(n) = O(1) then f(n) = O(n)

The other direction is not true.
That said, it is customary to give the tighter bound, in this case it's O(1), but it is true that it is ALSO O(n).

Regards,
Zachm