確定此循環的BIg 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來表示日誌庫2）。