Determining the BIg O notation of this loop

Question

for(i=0;i<n;i+=2) {
  for(j=1;j<=n;j*=2) {
      printf(“%d,%d\n”,i,j);
    }
}

What would be the Big O notation of this loop?

Possible duplicate of [Big O, how do you calculate/approximate it?](http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Paul Hankin, Jul 23 '16 at 06:01

Tim Biegeleisen · Accepted Answer · 2016-07-23T05:56:30.770

4

The outer loop will do n/2 iterations, and each inner loop will do lg_2(n) iterations.

The overall running time should be O(n*lgn) (here I use lg to represent log base 2).

edited Jul 23 '16 at 05:56

answered Jul 23 '16 at 05:55

Tim Biegeleisen

1 Answers1