Time complexity analysis. while loop with inner for loop [duplicate]

Question

This question already has an answer here:

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

Closed 8 years ago.

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!