主定理用于求递推方程的阶。
设a>=1, b>1为常数，f(n)为函数，T(n)为非负整数，且
T(n) = aT(n/b) + f(n)
（注意a、b取值范围）
a代表递归调用子问题的个数(子问题数>=小于原问题，故a>=1)n / b代表子问题规模（子问题规模一定是递减的，否则问题无法收敛，故b>1）f(n)代表把子问题的解组合成原问题的总工作量有以下三种结果：
若f(n) = O(nlogba-ε)，ε>0，则T(n) = Θ(nlogba)若f(n) = Θ(nlogba)，则T(n) = Θ(nlogba logn)若f(n) = Ω(nlogba+ε)，ε>0，且对于某个常数c<1和所有充分大的n有af(n/b) <= cf(n)，则T(n) = Θ(f(n)) 例1T(n) = 9T(n/3) + n
a = 9, b = 3, logba = 2，符合1式，得T(n) = Θ(n2)
例2T(n) = T(2n/3) + 1
a = 1, b = 3/2, logba = 0，符合2式，得T(n) = Θ(logn)
例3.1T(n) = 3T(n/4) + nlogn
a = 3, b = 4, logba = log43
且要使a * f(n/b) = 3 * (n/4) * log (n/4) <= cnlogn， 得c>=3/4 - 3/(2logn)，c>=3/4即对充分大的n成立。
符合3式，得T(n) = Θ(nlogn)
例3.2T(n) = 2T(n/2) + nlogn
a = 2, b = 2, logba = 1，貌似符合3式；
但事实上找不到ε>0使得nlogn = Ω(nlogba+ε)成立，因为logn的阶低于任何幂函数nε（ε>0）。
所以并不符合3式，不能用主定理。应使用递归树求解：
T(n) = nlogn + n(logn-1) + n(logm-2) + …… = O(nlog2n)