CODEWITHSUNDEEP
javabig-o
user3251142
user3251142

Reputation: 175

Is this code O(n) or O(logn)?

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

Answers (4)

rgettman
rgettman

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

user902383
user902383

Reputation: 8640

your code has complexity O(n), O(n)/3 == a * O(n) == O(n)

Upvotes: 2

Codor
Codor

Reputation: 17605

The running Time is O(n) (in unit complexity measure).

Upvotes: 1

pizzaEatingGuy
pizzaEatingGuy

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

Related Questions