递归式代入法

猜测给出希望证明的增长率，归纳代入检验递推是否会把它推高。需要的松弛可能来自主项常数，也可能来自一个精心选择的低阶修正项；调整的目的，是让每次递推都留下足够空间支付本层工作。

递归参数必须严格更小。对一般整数规模，可以用所有较小情形作为归纳假设；对上面的幂点序列，也可以对高度 $h$ 作普通归纳。两种写法都要覆盖实际递归能到达的基例。

图中 $\log$ 以2为底，归纳假设只用于 $2\le m<n$ 的幂点；基例门槛 $c_0$ 可取为前述 $t_0+1$。这样图示的常数条件与规模2的归纳起点一致。

何时真的需要低阶修正 ​

对 $T(1)=1$、$T(n)=2T(n/2)+1$，直接猜 $T(n)\le cn$ 会给出 $T(n)\le cn+1$，无论怎样加大 $c$，这一归纳步骤都没有闭合。换成 $T(n)\le cn-d$，便得到

只要 $d\ge 1$。再取 $c\ge d+1$ 处理规模1基例，线性上界就得到证明。事实上此递推的精确解为 $2n-1$，修正项正好对应树中内部节点数比叶子数少一。

取整与基例区间 ​

若 $T(n)=T(\lfloor n/2\rfloor )+1$ 对 $n\ge 2$ 成立，且 $T(0),T(1)=O(1)$，取整不会破坏参数严格下降。可以直接逐次减半计数，也可以加强为覆盖 $n=0,1$ 的 $c{\log }_2(n+1)+d$ 后作归纳。只猜 $cn$ 虽可能得到真上界，却没有说明对数阶。

上界证明应把子问题代入上界，下界证明应代入下界；有减项时，还须检查不等式方向和符号。只在若干规模上数值吻合，是寻找猜测的线索，并未覆盖所有递归规模。

递归树法理路递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。和主定理可以产生候选增长率，代入法负责检查常数、基例和误差项。加入一个修正项之后，仍应说明它在目标渐近范围内不改变主阶。

有界搜索树理路有界搜索树Bounded search tree对局部障碍作完备分支，并让参数预算在每条分支严格下降。按参数 $k$ 递推，须区分参数函数与输入长度上的多项式因子。工作—深度模型理路Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。又为同一并行算法建立 $W(n)$ 和 $D(n)$ 两条递推：子问题的工作相加，独立子问题的深度取最大。代入技巧相同，但待证对象和组合规则要分别写清。