主定理用于解决形如以下形式的递归算法的时间复杂度：
T
(
n
)
=
a
T
(
n
/
b
)
+
f
(
n
)
T(n) = aT(n/b) + f(n)
T(n)=aT(n/b)+f(n)
a a a为子问题个数， b b b为子问题的规模
其中需满足 a ≥ 1 , b > 1 a \geq 1,b > 1 a≥1,b>1
则答案有三种情况：
简化一下，即为比较 f ( n ) f(n) f(n) 和 O ( n l o g b a ) O(n^{log_ba}) O(nlogba) 的大小，取大的，若是相同就加上 l o g n log n logn 的复杂度。
T
(
n
)
=
T
(
n
/
2
)
+
O
(
1
)
T(n) = T(n/2) + O(1)
T(n)=T(n/2)+O(1)
分析：
a
=
1
,
b
=
2
,
a = 1 ,b = 2,
a=1,b=2,基准函数
O
(
n
l
o
g
b
a
)
=
O
(
n
0
)
=
O
(
1
)
O(n^{log_{b}a}) = O(n ^ 0) = O(1)
O(nlogba)=O(n0)=O(1)
适用于Case3，即
T
(
n
)
=
O
(
l
o
g
n
)
T(n) = O(log n)
T(n)=O(logn)
T ( n ) = 2 T ( n 2 ) + O ( 1 ) T(n)=2T(\frac{n}{2})+O(1) T(n)=2T(2n)+O(1)
分析： a = b = 2 , f ( n ) = O ( 1 ) a=b=2,f(n)=O(1) a=b=2,f(n)=O(1) ,基准函数 O ( n l o g 2 2 ) = Θ ( n ) O (n^{log_{2}2})=\Theta (n) O(nlog22)=Θ(n) ，适用于Case1,所以 T ( n ) = O ( n l o g b a ) = O ( n ) T(n)=O (n^{log_{b}a})=O (n) T(n)=O(nlogba)=O(n)
T
(
n
)
=
3
T
(
n
/
4
)
+
O
(
n
)
T(n)=3T(n/4)+O(n)
T(n)=3T(n/4)+O(n)
O
(
n
log
b
a
)
=
O
(
n
log
4
3
)
=
O
(
1
)
<
O
(
n
)
O(n^{\log_ba}) = O(n^{\log_43}) = O(1)
所以复杂度为
O
(
n
)
O(n)
O(n)