确定这个循环的大 O 符号

Question

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

这个循环的大 O 表示法是什么？

Answer 1

外循环将进行 n/2 次迭代，每个内循环将进行 lg_2(n) 次迭代。

整体运行时间应该是O(n*lgn)（这里我用lg表示log base 2）。