主方法求解递归算法复杂度

假设有递推关系式

其中，n为问题规模，a为递推的子问题数量，n/b为每个子问题的规模（假设每个子问题的规模基本一样），f(n)为递推以外进行的计算工作。

情形一

如果存在常数，有

，并且是多项式的小于

那么

情形二

如果存在常数k ≥ 0，有

那么

情形三

如果存在常数，有

，并且是多项式的大于

同时存在常数以及充分大的，满足

那么