Reputation: 175
It's only checking the for loop 1/3n times, so it's still technically linear I guess? However I don't really understand why it wouldn't be O(logn), because many times a code with O(logn) running time ends up checking around 1/3n. Does O(logn) always divide the options by 2 every time?
int a = 0;
for (int i = 0; i < n; i = i+3)
a = a+i;
Upvotes: 0
Views: 129
Reputation: 178363
With time-complexity analysis, constant factors do not matter. You could do 1,000,000 operations per loop, and it will still be O(n). Because the constant 1/3 doesn't matter, it's still O(n). If you have n
at 1,000,000, then 1/3 of n
would be much bigger than log n
.
From the Wikipedia entry on Big-O notation:
Let k be a constant. Then:
O(kg) = O(g) if k is nonzero.
Upvotes: 2
Reputation: 880
It is order of n O(n)
and not O(logn)
.
It because the run time increases linearly with the increase in n
For more information take a look at this graph and hopefully you will understand why it is not logn https://www.cs.auckland.ac.nz/software/AlgAnim/fig/log_graph.gif
Upvotes: 1