时间复杂度 - 嵌套 for 循环

Question

对于给定的代码，bigO 表示法的时间复杂度是多少：

for(i=n; i >= 1; i /=2)
 for(j=i; j>=1; j/=2)
     x = i+j;

第一个循环运行Log N次，第二个循环呢？是 (Log N * Log N) 吗？

我很困惑。

谢谢

Answer 1

渐近地，我们可以说第二个循环的复杂度是 O(logn) 并且在第一个循环的每次迭代中，第二个循环迭代一次，所以复杂度将是 logn*logn 即 (logn)^2

Time Complexity - nested for loop