嵌套循环的复杂度除以2

Question

我试图找出使用Big O表示法的for循环的复杂性.我之前在其他课程中已经完成了这个,但是这个比其他课程更严格,因为它是在实际的算法上.代码如下:

for(i=n ; i>1 ; i/=2) //for any size n
{
    for(j = 1; j < i; j++)
    {
      x+=a
    }
}

我到了第一个循环是O(log_2(n)).至于第二个循环,我有点迷路!感谢您在分析中提供的帮助.

Answer 1

内循环的迭代总数为 n + n/2 + n/4 + ... + 1，大约为 2n。所以复杂度是O(n)。