您需要一点数学才能看到。内部循环迭代
Θ(1 + log [N/(i+1)])时间（
1 +因为for是必需的
i >= N/2，
[N/(i+1)]= 1对数为0，但是循环迭代一次）。
j所采用的值
(i+1)*2^k，直到它至少一样大
N，并且
(i+1)*2^k >= N <=> 2^k >= N/(i+1) <=> k >= log_2 (N/(i+1))
使用数学除法。因此，将更新
j *= 2称为
ceiling(log_2 (N/(i+1)))时间，并将条件称为检查
1 + ceiling(log_2(N/(i+1)))时间。这样我们就可以写出全部工作
N-1 N ∑ (1 + log (N/(i+1)) = N + N*log N - ∑ log ji=0 j=1= N + N*log N - log N!
现在，斯特林的公式告诉我们
log N! = N*log N - N + O(log N)
因此我们发现完成的总工作确实是
O(N)。
