主定理适用于递归复杂度计算。

标准版：

a,ba,b 是常数，f(n)f(n) 为额外附加值函数 T(n)T(n) 为递归式 T(n)=aT(nb)+f(n) (a>0,b>1)T(n)=aT(\frac{n}{b})+f(n)\ (a>0,b>1)，就有：

1. 当 f(n)=O(n(log⁡ba)−ϵ)f(n)=\mathcal{O}(n^{(\log_ba)-\epsilon}) 其中 ϵ>0\epsilon>0 是一个常数（相当于 log⁡ba>f(n)\log_ba>f(n)），则有 T(n)=Θ(nlog⁡ba)T(n)=\Theta(n^{\log_ba})；
2. 当 f(n)=Θ(nlog⁡ba)f(n)=\Theta(n^{\log_ba})，则有 T(n)=Θ(nlog⁡balog⁡n)T(n)=\Theta(n^{\log_ba}\log n)；
3. 当 f(n)=Ω(n(log⁡ba)+ϵ)f(n)=\Omega(n^{(\log_ba)+\epsilon}) 其中 ϵ>0\epsilon>0 是一个常数（相当于 log⁡ba<f(n)\log_ba<f(n)），且对于一个常数 c<1c<1 和所有足够大的 nn 有 af(nb)≤cf(n)af(\frac{n}{b})\leq cf(n)（这一条件在这里可以暂时忽略不看，但在证明时起到至关重要的作用），则有 T(n)=Θ(f(n))T(n)=\Theta(f(n)).
4. 当 f(n)=Θ(nlog⁡balog⁡kn)f(n)=\Theta(n^{\log_ba}\log^kn) 其中 k≥1k\geq1 是一个常数，则有 T(n)=Θ(nlog⁡balog⁡k+1n)T(n)=\Theta(n^{\log_ba}\log^{k+1}n)；

举例：

例一：T(n)=4T(n2)+nT(n)=4T(\frac{n}{2})+n，此时 a=4,b=2,ϵ=1a=4,b=2,\epsilon=1，那么 log⁡ba=log⁡24=2,f(n)=O(nlog⁡ba−ϵ)=O(n2−1)\log_ba=\log_24=2,f(n)=\mathcal{O}(n^{\log_ba-\epsilon})=\mathcal{O}(n^{2-1})，f(n)f(n) 成立，所以 T(n)=Θ(nlog⁡ba)=Θ(n2)T(n)=\Theta(n^{\log_ba})=\Theta(n^2)。

例二：T(n)=2T(n2)+nT(n)=2T(\frac{n}{2})+n，此时 a=2,b=2a=2,b=2，那么 log⁡ba=log⁡22=1,f(n)=Θ(nlog⁡ba)=Θ(n)\log_ba=\log_22=1,f(n)=\Theta(n^{\log_ba})=\Theta(n)，f(n)f(n) 成立，所以 T(n)=Θ(nlog⁡balog⁡n)=Θ(nlog⁡n)T(n)=\Theta(n^{\log_ba}\log n)=\Theta(n\log n)。

例三：T(n)=4T(n2)+n3T(n)=4T(\frac{n}{2})+n^3，此时 a=4,b=2,ϵ=1a=4,b=2,\epsilon=1，那么 log⁡ba=log⁡24=2,f(n)=Ω(nlog⁡ba+ϵ)=Ω(n2+1)\log_ba=\log_24=2,f(n)=\Omega(n^{\log_ba+\epsilon})=\Omega(n^{2+1})，对于 c=23c=\frac{2}{3} 和够大的 nn，(af(nb)=4(n2)3=4(n38)=n32)≤(cf(n)=2n33)\left(af(\frac{n}{b})=4(\frac{n}{2})^3=4(\frac{n^3}{8})=\frac{n^3}{2}\right)\leq \left(cf(n)=\frac{2n^3}{3}\right)，f(n)f(n) 成立，所以 T(n)=Θ(f(n))=Θ(n3)T(n)=\Theta(f(n))=\Theta(n^3)。

例四：T(n)=2T(n2)+nlog⁡nT(n)=2T(\frac{n}{2})+n\log n，此时 a=2,b=2,k=1a=2,b=2,k=1，那么 log⁡ba=log⁡22=1,f(n)=Θ(nlog⁡balog⁡kn)=Θ(nlog⁡n)\log_ba=\log_22=1,f(n)=\Theta(n^{\log_ba}\log^kn)=\Theta(n\log n)，f(n)f(n) 成立，所以 T(n)=Θ(nlog⁡balog⁡k+1n)=Θ(nlog⁡2n)T(n)=\Theta(n^{\log_ba}\log^{k+1}n)=\Theta(n\log^2 n)。

简化版

将一个规模为 nn 的问题，通过分治得到 aa 个规模为 nb\dfrac{n}{b} 的子问题，每次递归进行的计算为 O(nd)O(n^d)，满足如下形式：

T(n)=a⋅T(nb)+O(nd)T(n)=a\cdot T(\dfrac{n}{b})+O(n^d)

则 T(n)T(n) 满足：

T(n)={O(nd)d>log⁡baO(ndlog⁡n)d=log⁡baO(nlog⁡ba)d<log⁡baT(n)=\begin{cases} O(n^d) & d> \log_b a\\ O(n^d\log n) & d= \log_b a\\ O(n^{\log_b a}) & d<\log_b a\\ \end{cases}

---

例如：

有递归式：

T(n)={O(1)n=12T(n2)+notherwise.T(n)=\begin{cases} O(1) & n=1\\ 2T(\dfrac{n}{2})+n & \text{otherwise.} \end{cases}

则有 a=2,b=2,d=1a=2,b=2,d=1。

∵1=log⁡22∴T(n)=O(n1log⁡n)=O(nlog⁡n)\begin{array}{ll} \because 1=\log_22\\ \therefore T(n)=O(n^1\log n)=O(n\log n) \end{array}

---

另一例子：

T(n)={O(1)n=12T(n2)+1otherwise.T(n)=\begin{cases} O(1) & n=1\\ 2T(\dfrac{n}{2})+1 & \text{otherwise.} \end{cases}

则有 a=2,b=2,d=0a=2,b=2,d=0。

∵0<log⁡22∴T(n)=O(nlog⁡22)=O(n)\begin{array}{ll} \because 0<\log_22\\ \therefore T(n)=O(n^{\log_2 2})=O(n) \end{array}

---

例三：

T(n)={O(1)n=12T(n2)+nlog⁡notherwise.T(n)=\begin{cases} O(1) & n=1\\ 2T(\dfrac{n}{2})+n\log n & \text{otherwise.} \end{cases}

则有 a=2,b=2,d=1a=2,b=2,d=1。

∵1=log⁡22∴T(n)=O(n1log⁡n⋅log⁡n)=O(nlog⁡2n)\begin{array}{ll} \because 1=\log_22\\ \therefore T(n)=O(n^1\log n\cdot \log n)=O(n\log^2 n) \end{array}