このループのBIg O表記の決定

Question

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

このループのBig O表記法は何ですか？

Answer 1

外側のループはn/2の反復を行い、内側のループはそれぞれlg_2(n)の反復を行います。

全体の実行時間はO(n*lgn)（ここではログベース2を表すにはlgを使用します）。