Big O complexity of this loop

Question

If I have

int i;
for(i = 1; i < n; i *= 2) //n is the size of an array passed to the function
{
  //O(1) code here
}

What is the Big O complexity? The "i *= 2" bit is confusing me. I tried operation counting but now I'm even more confused.

Look at the last slide of [this](http://faculty.kfupm.edu.sa/ics/jauhar/ics202/Unit03_ComplexityAnalysis1.ppt). — Mohamed Ennahdi El Idrissi, Jun 02 '14 at 14:36

score 3 · Accepted Answer · answered Jun 01 '14 at 16:05

3

It looks like O(log(n)), because you iterate not over the whole sequence, but use power-of-two steps.

answered Jun 01 '14 at 16:05

Ashalynd

score 1 · Answer 2 · edited Jun 01 '14 at 17:49

1

complexity is O(log₂(N))

Basically your 'i' doubles every iteration so after 1 iteration it's 2, then 4, then 8. so if n = 2⁸ then the loop will iterate (roughly) 8 times.

edited Jun 01 '14 at 17:49

Donal Fellows

answered Jun 01 '14 at 16:05

Zach Fewtrell

To be clear, this is the number of loop iterations, not the big-O complexity. – crockeea Jun 01 '14 at 16:07
Eric, can you elaborate on the difference? – Zach Fewtrell Jun 01 '14 at 16:08
1

@Ashalynd's answer has the big-O complexity: it is O(log(n)) (no base, no subtraction). O(log2(N)-1) = O(log2(N)) = O(log(N))` (any base), and the canonical representative of this complexity class is `O(log(N))`. Actually, upon looking at your answer more closely, it appears you have `log2(N)-log2(N) = 0` as the complexity. – crockeea Jun 01 '14 at 16:11
Thanks - I made some minor edits to make it more clear. – Zach Fewtrell Jun 01 '14 at 16:16

score 1 · Answer 3 · edited May 23 '17 at 10:32

1

You'd be halving the steps each time, so you'd end up with O(log n), where n is the total number of iterations. See this: What would cause an algorithm to have O(log n) complexity?

edited May 23 '17 at 10:32

Community

answered Jun 01 '14 at 16:08

Nav

AbcAeffchen · Answer 4 · 2015-04-02T14:10:26.703

1

The complexity is O(log n).

You can rewrite the loop to for(x = 0; pow(2,x) < n; x++) so x < log n. (pow should compute 2^x)

edited Apr 02 '15 at 14:10

answered Jun 01 '14 at 16:13

AbcAeffchen

4 Answers4