O(n) runtime algorithm

Question

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

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

Answer 1

Your professor was right, the running time is O(n).

In the i-th iteration of the outer while-loop, when we have i=2^k for k=0,1,...,log n, the inner while-loop makes O(i) iterations. (When I say log n I mean the base-2 logarithm log_2 n.)

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

Because 2^{log n} = n, the total running time is O(n).

For the interested, here's a proof that the powers of two really sum to what I claim they sum to. (This is a very special case of a more general result.)

Claim. For any natural k, we have 1+2+2^2+...+2^k = 2^{k+1}-1.

Proof. 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 cancel out, except for i=0 and i=k+1, and we are left with 2^{k+1}-1. QED.