java – 具有log n复杂度的外部循环的两个依赖循环的复杂度

计算这个算法的复杂性：

for(i=n; i>1;i=i/2)
   for(j=i;j<n;j++){
         statement;
   }

以前我对此主题做了些什么：

第一个循环运行logn时间.
第二个循环运行n-i次,i从n开始,并在每个外循环迭代中改变为i / 2.所以内循环运行如下：

n-n                             0 times

n - n/2                        n/2 times

n - n/4                        3n/4 times

n - n/8                        7n/8 times

n - n/16                     15n/16 times

等等

n – 1次

所以一般的术语是n *((2 ^ n)-1)/(2 ^ n)

现在这个序列不是算术和几何.因此,n / 2 *(a l)的公式不能应用于它.如何进一步处理此解决方案或错误,那么正确的方法是什么.

注意：如果应用n / 2 *(a l),则得到的复杂度为-n /(2 ^ n)= O(2 ^ n).