递归替代证明中的大 theta 符号
Big theta notation in substitution proofs for recurrences
通常在 CLRS 中，当通过替换证明递归时，会将 Ө(f(n)) 替换为 cf(n)。
例如，在第 91 页，重复
T(n) = 3T(⌊n/4⌋) + Ө(n^2)
证明中是这样写的
T(n) <= 3T(⌊n/4⌋) + cn^2
但是 Ө(n^2) 不能代表 cn^2 + n 吗？那不会使这样的证明无效吗？在进一步的证明中，声明
T(n) <= (3/16)dn^2 + cn^2
<= dn^2
达成。但是如果用cn^2 +n代替，就会变成下面的
T(n)<= (3/16)dn^2 + cn^2 + n
如果是这样，还能证明 T(n) <= dn^2 吗？这样的低阶项在通过替换证明递归时无关紧要吗？
是的，没关系。
如果 n 足够大，T(n) <= (3/16)dn^2 + cn^2 + n 仍然小于或等于 dn^2。因为随着 n 趋于无穷大，等式的两侧具有相同的增长率（即 n^2），所以如果成本函数中的低阶项数量不变，则低阶项将无关紧要。但如果它们的数量不是恒定的，那就是另一回事了。
编辑：随着 n 趋于无穷大，您会发现适合 T(n) <= (3/16)dn^2 + cn^2 + n 小于或等于 dn^2 的 d 和 c，例如 d = 2 和 c = 1
通常在 CLRS 中，当通过替换证明递归时，会将 Ө(f(n)) 替换为 cf(n)。
例如，在第 91 页，重复
T(n) = 3T(⌊n/4⌋) + Ө(n^2)
证明中是这样写的
T(n) <= 3T(⌊n/4⌋) + cn^2
但是 Ө(n^2) 不能代表 cn^2 + n 吗？那不会使这样的证明无效吗？在进一步的证明中，声明
T(n) <= (3/16)dn^2 + cn^2
<= dn^2
达成。但是如果用cn^2 +n代替，就会变成下面的
T(n)<= (3/16)dn^2 + cn^2 + n
如果是这样，还能证明 T(n) <= dn^2 吗？这样的低阶项在通过替换证明递归时无关紧要吗？
是的，没关系。
如果 n 足够大，T(n) <= (3/16)dn^2 + cn^2 + n 仍然小于或等于 dn^2。因为随着 n 趋于无穷大，等式的两侧具有相同的增长率（即 n^2），所以如果成本函数中的低阶项数量不变，则低阶项将无关紧要。但如果它们的数量不是恒定的，那就是另一回事了。
编辑：随着 n 趋于无穷大，您会发现适合 T(n) <= (3/16)dn^2 + cn^2 + n 小于或等于 dn^2 的 d 和 c，例如 d = 2 和 c = 1