Time complexity analysis. while loop with inner fo

Question

This question is an exact duplicate of:

• Time complexity analysis. choosing operator for counting number of times a line of code runs 1 answer

I'm trying to find the number of times this code runs. On the right I have my attempt at the code. I'm am not sure about the loops. Here is the code:

                         times
sum = 0                    1
i = 1                      1 
while i ≤ n                log n + 1
 sum = sum + i             n log n
 i = 2i                    log n
return sum                  1

=> n log n + 2 log n + 4

and thereby: O(n log n)

is this correct ?

Answer 1

No, your analysis is incorrect. Note that each iteration of the inner loop does O(1) work, so the total time complexity can be found by multiplying the number of loop iterations by O(1).

In this case, the loop runs for O(log n) iterations, since i can only double O(log n) times before it exceeds n. Therefore, the total time complexity is O(log n).

Hope this helps!