What complexity is that a nested loop but the inner loop starts from i and ends with half?-CodePudding

for ( i = 1; i <= n; i  ) {
   for ( j = i; j >= 1; j = j / 2) {
     // some code
   }
}

Assume that the code of the inner loop is constant. I thought its O(n^2) Here is my opinion regarding this question. I think that the run time of the inner loop is logi 1 so I got the formula: (log1 1) (log2 1) ... (logn 1) then get O(n^2)

but I saw another solution for this is logi and then the answer is O(nlogn)

then I get confused about which one is correct? I think that I'm correct but I'm not sure. So if I'm wrong plz convince me why the second is correct? I know that the difference between these two is the number of times the inner loop executes

CodePudding user response：

The inner loop has the time complexity of O(log(i)), and the outer loop has the time complexity of O(n). The overall time complexity is O(nlog(n)).

We can also get the time complexity with your calculation:

(log1 1) (log2 1) ... (logn 1) <= (logn 1) (logn 1) ... (logn 1) = n * log(n) n = O(nlog(n)). We can discard n because nlog(n) is the dominating in the polynomial n * log(n) n. The calculated time complexity is O(nlog(n)) as well.