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 ?