Determine the time complexity of a basic code

[Song Tung]

Can anyone please explain why this is O(n). And if I change the increment of i to i++. Will the time complexity of the code change to O(n^2)?

  int sum = 0;
  for(int i = 1; i < N; i = i * 2)
    for(int j = 0; j < i; j++)
        sum++;

[TheIdeasMan]

Hi,

That looks to me like n log n.

The outer loop doubles each time: 1,2,4, 8 ... that's the log part. The inner loop is O(n)

Will the time complexity of the code change to O(n^2)?

Yes.

[mbozzi]

That looks to me like n log n.

The inner loop only executes i times.

In total, the outer loop executes the inner loop i times for each i in series 2^0, 2^1, ..., 2^(ceil(lg(N)) - 1) (the first ceil(lg(N)) powers of 2).

The resulting sum is hard to write in this forum, but in natural language it's something like
sum from p = 0 to (ceil(log2(N)) - 1) of (sum from i = 1 to 2^p of 1)
Which is in O(N).

[TheIdeasMan]

@mbozzi

Hi Max,

My bad, I should learn to read one day !! Although in my pathetic defense, this is one reason why I don't like variables i and j

Also, Song Tung, it might have been interesting to run this code: does sum == N at the end ?

[Song Tung]

Thanks for the replies. I think I've finally understood it now. I just need final confirmation for the second question, when I change "i = i*2" to "i++", it's O(n^2) right?

[mbozzi]

Yes!

...if you were to write out the sum, you'd get the sum of the first N natural numbers, which is in O(n^2).