Master's Theorem states the asymptotic complexity of divide-and-conquer algorithms.

主定理（master theorem） ：假设递推关系式为：

T(n) = a T(\frac{n}{b}) + f(n)

其中，n为问题规模、a为递推子问题数量、\frac{n}{b}为每个子问题的规模（假设各子问题规模相同）、函数f(n)为递推之外的计算量，常数a \geq 1、常数b \gt 1、T(n)为非负整数，则

假设存在一个正实数\epsilon使得f(n)的时间复杂度属于大O类的n^{\log_b a - \epsilon}那么递归函数的渐近行为满足\Theta(n^{\log_b a})

若存在常数k \geq 0，使得f(n) = \Theta (n^{\log_{b}(a)} \log^{k}n)，则T(n) = \Theta (n^{\log_{b}a} \log^{k + 1}n)

若存在一个正实数\epsilon > 0使得函数f满足f(n) ∈ Ω\left( n^{\log_b a + \epsilon} \right)并且当n足够大时有a·f\left( \frac{n}{b} \right) ≤ c·f\left( n\right)其中c < 1是一个正实数值，则递归关系式的时间复杂度为$T\left( n\