What is the complexity of this code, the loop enclosed in it doubles the counter again?

Question

The book "Interviews with programming" shows that the complexity of the program is below O (N), but I do not 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; } } 

Answer 1

You need a little math to see this. The inner loop iterates Θ(1 + log [N/(i+1)]) times ( 1 + is required, since for i >= N/2 , [N/(i+1)] = 1 and the logarithm is 0, but the cycle repeats once). j takes values (i+1)*2^k until it is at least N , and

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

using mathematical division. Therefore, updating j *= 2 is called ceiling(log_2 (N/(i+1))) times, and the condition is checked 1 + ceiling(log_2 (N/(i+1))) times. So we can record the overall 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) 

therefore, we find that the overall work performed is indeed O(N) .

Answer 2

The outer loop starts n times. Now it all depends on the inner cycle.
The inner loop is now complex.

Let's consider:

 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) 

Answer 3

@ Daniel Fisher answered correctly.

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

It means: