Is complexity for this loop O(1) or O(n)?Code:for ( int i = 0; i < 100; i++)
{
}
Printable View
Is complexity for this loop O(1) or O(n)?Code:for ( int i = 0; i < 100; i++)
{
}
O(n) as it would vary linearly with the number of times the loop is executed.
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
Why someone say this is O(1) and O(n) ?
I believe that analysis of this algorithm run in 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).Quote:
Originally Posted by Peter_APIIT
I disagree as Zachm's analysis looks correct to me. If the complexity of this algorithm is in O(n), then what is n?Quote:
Originally Posted by Peter_APIIT
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 :p).
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.
You don't need to claim ignorance ;), the following is always true:Quote:
Originally Posted by laserlight
The other direction is not true.Code:if f(n) = O(1) then f(n) = O(n)
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