substitution - 代入法的递归关系？

Question

我有：T(n) = T(n/2) + T(n/4) + T(n/8) + cn；c > 0。

这是我的归纳步骤：想证明 T(n) 在 O(n) 中，即一些 d > 0 和 n0 使得每个 n > n0 和 T(n) < dn

T(n) = T(n/2) + T(n/4) + T(n/8) + cn <= d(n/4) + d(n/4) + d (n/8) + cn = dn(7/8) + cn = dn(7/8) + cn <= dn ... = 8c <= d

我被基本情况卡住了，但这就是我的老师向我解释的方式：基本情况：需要 n0 足够小以便尝试。尝试 n0 = 8 T(8) = T(4) + T(2) + T(1) + c8 <= 8T(4) + 8T(2) + 8T(1) + C8 < d8

有人可以向我解释基本情况吗？谢谢！

Answer 1

对于基本情况T(8)，我们可以假设操作是有限的。所以运行时间将是O(1)（恒定时间）。因为您可以计算操作次数。