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

blazs · Accepted Answer · 2017-04-07 09:14:41Z

9

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.

edited Apr 7, 2017 at 9:14

answered Apr 3, 2016 at 9:07

blazs

4,85528 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Luka Rahne Over a year ago

How result is not O(n)?

blazs Over a year ago

Sorry, it was a typo. It is O(n). :)

Marco A. Over a year ago

Correct. I'm adding a second explanation here for clarity's sake

cmaster - reinstate monica Over a year ago

It should be noted that this is precisely the reason why we usually grow buffers by powers of two: It makes the work needed to repeatedly copy over existing buffer contents O(N), which is much nicer than the O(N^2) that is associated with growing a buffer by a constant amount of space.

Collectives™ on Stack Overflow

O(n) runtime algorithm

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related