algorithm - 两个带有连接变量的for循环的时间复杂度计算

Question

这个的时间复杂度是多少:

for(k=1;K<=n;k*=2)
   for(j=1;j<=k;j++)
     sum++

为此我认为
1. Outer Loop会运行logn次
2. 内循环也会运行 logn 次。
因为我认为内循环 j 与 k 相关。所以 k 运行了多少，j 的运行时间也一样。
所以总计 = O(logn * logn)

但在文本中他们给出了 total= O(2n-1)。
你能解释一下吗

Answer 1

当k为1时(sum++)运行1次

当k为2时(sum++)运行2次

当k为4时(sum++)运行4次

当 k 为 n = 2^k (sum++) 运行 2^k 次

所以我们必须计算

1+2+4+ ... + 2^k = 2^0 + 2^1 + 2^2 + .... + 2^k = (1 - 2^(k+1))/(1-2)

因为我们把 n = 2^k 所以:

k = log(n)

2^(log(n)) = n^(log(2))

2* 2^k -1 = 2*n - 1