What is the complexity of this code whose nested f

问题:

In the book Programming Interviews Exposed it says that the complexity of the program below is O(N), but I don't understand how this is possible. Can someone explain why this is?

int var = 2;
for (int i = 0; i < N; i++) {
   for (int j = i+1; j < N; j *= 2) {
      var += var;
   }
}

回答1:

You need a bit of math to see that. The inner loop iterates Θ(1 + log [N/(i+1)]) times (the 1 + is necessary since for i >= N/2, [N/(i+1)] = 1 and the logarithm is 0, yet the loop iterates once). j takes the values (i+1)*2^k until it is at least as large as N, and

(i+1)*2^k >= N <=> 2^k >= N/(i+1) <=> k >= log_2 (N/(i+1))

using mathematical division. So the update j *= 2 is called ceiling(log_2 (N/(i+1))) times and the condition is checked 1 + ceiling(log_2 (N/(i+1))) times. Thus we can write the total work

N-1                                   N
 ∑ (1 + log (N/(i+1)) = N + N*log N - ∑ log j
i=0                                  j=1
                      = N + N*log N - log N!

Now, Stirling's formula tells us

log N! = N*log N - N + O(log N)

so we find the total work done is indeed O(N).

回答2:

Outer loop runs n times. Now it all depends on the inner loop.
The inner loop now is the tricky one.

Lets follow:

i=0 --> j=1             ---> log(n) iterations
...
...
i=(n/2)-1 --> j=n/2     ---> 1 iteration.
i=(n/2) -->   j=(n/2)+1 --->1 iteration.

---

i > (n/2)            ---> 1 iteration
(n/2)-1 >= i > (n/4) ---> 2 iterations
(n/4) >= i > (n/8)   ---> 3 iterations
(n/8) >= i > (n/16)  ---> 4 iterations   
(n/16) >= i > (n/32) ---> 5 iterations

(n/2)*1 + (n/4)*2 + (n/8)*3 + (n/16)*4 + ... + [n/(2^i)]*i

   N-1                                   
 n*∑ [i/(2^i)] =< 2*n
   i=0  

--> O(n)

回答3:

@Daniel Fischer's answer is correct.

I would like to add the fact that this algorithm's exact running time is as follows:

Which means: