为什么这个递归关系是 O(1)？

Question

重写下面已解决的问题以供参考：

原问题：

T(n) = 2T(n - 1) - 1, if n > 0
1,                    otherwise

第一次迭代

T(n) = 2T(n - 1) - 1
T(n - 1) = 2T(n - 1 - 1) - 1 
T(n - 1) = 2T(n - 2) - 1

第二次迭代

T(n) = 2(2T(n - 2) - 1) - 1
T(n) = 4T(n - 2) - 2 - 1
T(n) = 4T(n - 2) - 3
T(n - 2) = 2T(n - 2 - 1) - 1
T(n - 2) = 2T(n - 3) - 1

第三次迭代

T(n) = 4(2T(n - 3) - 1) - 3
T(n) = 8T(n - 3) - 4 - 3
T(n) = 8T(n - 3) - 7
T(n - 3) = 2T(n - 3 - 1) - 1
T(n - 3) = 2T(n - 4) - 1

第 4 次迭代

T(n) = 8T(n - 3) - 7
T(n) = 8(2T(n - 4) - 1) - 7
T(n) = 16T(n - 4) - 8 - 7
T(n) = 16T(n - 4) - 15

决赛table

At k=1, T(n) = 2T(n - 1) - 1
At k=2, T(n) = 4T(n - 2) - 3
At k=3, T(n) = 8T(n - 3) - 7
At k=4, T(n) = 16T(n - 4) - 15
        T(n) = 2ᴷT(n - k) - (2ᴷ - 1)
At k=n  T(n) = 2ᴺT(n - n) - (2ᴺ - 1)
        T(n) = 2ᴺT(0) - (2ᴺ - 1)
        T(n) = 2ᴺ - (2ᴺ - 1)
        T(n) = 2ᴺ - 2ᴺ + 1
        T(n) = 1

Answer 1

T(n) = 2T(n-1) -1
     = 2(2T(n-2)-1) - 1 = 4T(n-2)-3 = (2^2)T(n-2)-(2^2-1)
     = 2(4T(n-3)-3) - 1 = 8T(n-3)-7 = (2^3)T(n-3)-(2^3-1)
     ...
     = (2^n)T(n-n)-(2^n-1) = (2^n)1 - 2^n + 1 = 1

Answer 2

T(n) = 1 的归纳证明如下所示：

感应开始。

什么是 T(0)？ 1.

感应步骤。

假设对于任何 n >= 0，T(n) = 1。现在让我们看看声明是否适用于 T(n+1)。

T(n+1) = 2*T(n) - 1 = 2*1 - 1 = 1

结论。

T(n) = 1 对于所有自然数 n。而 1 在 O(1) 中。

你的错误。

我在你的计算中发现的第一个错误在这里：

T(n) = 2²(2T(n - 3) - 1) - 3
T(n) = 2³T(n - 3) - 2 - 3
                    ^ this should be a 4

为什么这个递归关系是 O(1)？

Why is this Recurrence Relation O(1)?

recursion

complexity-theory

big-o

time-complexity