为什么这个算法是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.