Karatsuba算法涉及递归关系。
通过递归树方法，可以近似地将T(n) = 3T(n/2) + n的大O设为T
然而，用代换法，我很难用递归树方法验证近似结果。
我只使用O(n)来表示lg 3。
替代方法：
Hypothesis -> T(n) <= cn where c is a positive constant
Proof -> T(n) <= 3c(n/2) + n
= cn + n但是证明的第二步表明我不能证明我的假设，因为n项。
我修改了证明的第二步
T(n) <= cn + n
= (c+1)n后来意识到我犯了一个错误，因为这个假设没有得到证实。
log3必须得到证明，而不是T(n) <= cn但答案是
T(n) <= (c+1)n是T(n) 最佳答案
在使用替换方法时，有时必须加强归纳假设，并猜测一个更复杂的表达式形式，该表达式的上界是递归。
试着猜测t（n）≤c0 nlg 3-c1n的形式，现在你正在减去c1n形式的某个项，你可能可以通过使用一些线性项来抵消后面加的n项来计算递归。
例如：
T（n）≤3T（n/2）+n
小于等于3（c0（n/2）lg 3-c1（n/2））+n
=3（c0（n/2）lg 3）-3c1n/2+n
现在，选择c1使-3c1 n/2+n=-c1n。
-3c1n/2+n=-c1n
-3C1/2+1=-C1
-3C1+2=-2C1
2=C1
选择c1可以让你成功地取消+n项，让归纳法成功地工作。
希望这有帮助！