time-complexity - 无限运行程序的时间复杂度

Question

以下程序段的时间复杂度是否可能为 O(2^n)？我很困惑

n=1;
for j=1 to n do
 output(j);
 n=2*n;
end {for}

Answer 1

不，这是 O(n)。

您只是将 n 提高到 2^n 次方。

这是因为循环的迭代次数是“n”，无论最终答案或其中的计算如何。