递归式代入法

代入法先根据递推展开、递归树、主定理或实验猜测渐近界，再用归纳法负责“封口”：假设所有更小规模已经满足目标界，验证本层递推不会突破它。真正的技巧是选择常数、加强命题并给猜测留出足够松弛；只写 $T(n)\le cn\log n$ 可能被低阶项卡住，加入 $-dn$ 或从足够大的 $n_0$ 开始常能闭合。上界与下界需分别选择归纳假设和常数。

证明 $T(n)=T(\lfloor n/2\rfloor )+1=O(\log n)$ 时，可对所有小于 $n$ 的规模做强归纳。直接猜 $T(n)\le cn$ 对某些递推虽真却过松，不能得到紧界；猜得过紧又可能因常数项失败。Big-O 证明只需对足够大 $n$ 成立，但基例区间必须覆盖所有递归会落到的值。下界证明方向相反，不能把不等式符号机械照搬。

若递归的非递归项从 $+n$ 变为 $+n+1$，形式陈述中的同一猜测可能被额外常数卡住；此时应调整常数、扩大基例区间，或在待证式中加入线性修正项，而不是重复套用原代数步骤。

不能在证明中把待证结论直接代回同规模 $T(n)$，归纳只适用于更小参数。忽略取整和基例有时不影响渐近结论，但严格证明需说明如何吸收；仅验证上界不能宣称 $\mathrm{\Theta }$。

递归关系公理库递推关系Recurrence relation用先前项规定序列当前项的关系。是对象，数学归纳法公理库数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。提供证明，渐近记号公理库渐近记号Asymptotic notation · Big O notation忽略常数和低阶项，比较函数在输入趋于无穷时的增长速度。表达结论。代入法核验递归树公理库递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。或主定理所得猜测，也能处理子问题规模不规则、带取整或需要低阶修正项的递推。

有界搜索树公理库有界搜索树Bounded search tree对局部障碍作完备分支，并让参数预算在每条分支严格下降。常以参数 $k$ 而非输入规模 $n$ 递推，代入时必须证明 $f(k)\mathrm{poly}(n)$ 中的指数只落在参数上。工作—深度模型公理库Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。又会为并行递归分别建立工作 $W(n)$ 与深度 $D(n)$ 两条递推；证明一个上界不能替代另一个。代入法仍是同一归纳技术，但变量、资源单位和待证保证必须先固定。