爲什麼這個算法O（N）？

Question

下面的C代碼顯然是O（N）（根據我的練習考試）。但是，我不確定爲什麼它是O（N）而不是O（Something * Something）。

void doit(int N) { 
    while (N) { 
     for (int j = 0; j < N; j += 1) { 
     } 
     N = N/2; 
    } 
} 

任何關心給我一些這種問題的見解？

在此先感謝！

Answer 1

因爲N + N/2 + N/4 + ... = 2N。