如何用几何图形法推导给定嵌套循环的时间复杂度？

你给出的代码如下：

for(int i = 1; i < n; i = i * 2)
    for(int j = 0; j < i; j++)
       // O(1) 操作

我们可以直接通过统计总执行次数推导时间复杂度：

• 首先看外层循环的i取值规律：i从1开始，每次乘2，直到小于n，所以i的取值序列为1, 2, 4, 8, ..., 2^k，满足2^k < n ≤ 2^(k+1)，外层循环总执行次数约为log₂n次。
• 内层循环的执行次数等于当前外层循环的i值，每次内层循环内部是O(1)操作，因此总操作次数就是所有i值的和：1 + 2 + 4 + 8 + ... + 2^k。
• 这是首项为1、公比为2的等比数列求和，根据等比数列求和公式可得总和为2^(k+1) - 1。结合之前的条件2^k < n，可推导出2^(k+1) < 2n，因此总操作次数小于2n -1，忽略常数项后时间复杂度就是O(n)。

如果用你提到的i、j坐标轴法推导也很直观：所有被执行到的(i,j)坐标点，会对应i轴上每次翻倍的纵向条形区域，所有区域包含的总点数就是上面计算的等比数列和，量级和n成正比，因此时间复杂度为O(n)。

内容的提问来源于stack exchange，提问作者freedom