Runtime of while loop pseudocode

Question

I have a pseudocode which I'm trying to make a detailed analysis, analyze runtime, and asymptotic analysis:

sum = 0
i = 1
while (i ≤  n){

    sum = sum + i
    i = 2i
}
return sum

My assignment requires that I write the cost/runtime for every line, add these together, and find a Big-Oh notation for the runtime. My analysis looks like this for the moment:

sum = 0                1
long i = 1                  1
while (i ≤  n){        log n + 1

   sum = sum + i       n log n
   i = 2i              n log n
}     
return sum             1

=> 2 n log n + log n + 4 O(n log n)

is this correct ? Also: should I use n^2 on the while loop instead ?

Answer 1

Because of integer arithmetic, the runtime is

O(floor(ln(n))+1) = O(ln(n)).

Let's step through your pseudocode. Consider the case that n = 5.

iteration#  i   ln(i)   n
-------------------------
1           1   0       5
2           2   1       5
3           4   2       5

By inspection we see that

iteration# = ln(i)+1

So in summary:

sum = 0             // O(1)
i = 1               // O(1)

while (i ≤  n) {    // O(floor(ln(n))+1)    

    sum = sum + i   // 1 flop + 1 mem op = O(1)
    i = 2i          // 1 flop + 1 mem op = O(1)
}
return sum          // 1 mem op = O(1)