Time complexity analysis. choosing operator for co

问题:

Analysing time complexity of this pseudocode. On the right my take on the number of times each line runs. I'm not sure whether to use log n , n log n , or simply n for the while-loop..please help

                                times
1 sum = 0                        1
2 i = 1                          1  
3 while i ≤ n                 log n + 1
4     for j = 1 to n           n log n
5     sum = sum + j            n log n
6 i = 2i                       log n
7 return sum                     1

this results in: 2 n log + 2log n + 4

and thereby : O(n log n)

is this correct ?

回答1:

If your while loop is:

3 while i < n                 log n + 1
4     for j = 1 to n           n log n
5        sum = sum + j         n log n
6     i = 2i                   log n

Then yes, you are correct in calculating the complexity. The complexity of the code is indeedO(nlogn).

Edit:
Though I am curious what you are trying to do here. You are calculating the sum of 1st n elements logn times.

Hence the return value would be something like n*(n+1)/2 * logn