O (n) runtime algorithm

Question

The algorithm below has runtime O(n) according to our professor, however I am confused about why it is not O(n log(n)) , since the outer loop can work up to log(n) times, and the inner loop can work up n times

 Algoritme Loop5(n) i = 1 while i ≤ nj = 1 while j ≤ ij = j + 1 i = i∗2 

Answer 1

Your professor was right, O(n) work time.

In the ith iteration of the external while loop, when we have i=2^k for k=0,1,...,log n , the internal while-loop iterates through O(i) . (When I say log n , I mean the logarithm of base-2 log_2 n .)

Operating time O(1+2+2^2+2^3+...+2^k) for k=floor(log n) . This sum is O(2^{k+1}) , which is O(2^{log n}) . (This follows from the formula for the partial sum of geometric series .)

Since 2^{log n} = n , the total runtime is O(n) .

For those interested, there is evidence that the forces of the two really add up to what I affirm, they add up. (This is a very special case of a more general result.)

claim. For any positive integer k we have 1+2+2^2+...+2^k = 2^{k+1}-1 .

Evidence. Please note that (2-1)*(1+2+2^2+...+2^k) = (2 - 1) + (2^2 - 2) + ... + (2^{k+1} - 2^k) , where all 2^i for 0<i<k+1 canceled, except i=0 and i=k+1 , and we are left with 2^{k+1}-1 . Q.E.D.