主定理

不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括阿克拉-巴兹方法。

支配理论

假设有递归关系式 T(n)=a T (n/b)+f(n)，其中 a≥ 1, b>1

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

情形一

如果存在常数 ε >0，有 f(n)=O(n^(l)og _(b)(a)-ε) （可不严谨的视作多项式地小于）

则 T(n)=Θ (n^(l)og _(b)a)

情形二

如果存在常数 ε ≥ 0，有 f(n)=Θ (n^(l)og _(b)alog ^(ε)n)

则 T(n)=Θ (n^(l)og _(b)alog ^(ε +1)n)

情形三

如果存在常数 ε >0，有 f(n)=Ω (n^(l)og _(b)(a)+ε) （多项式地大于）

同时存在常数 c<1 以及充分大的 n，满足 af(n/b)≤ cf(n)

则 T(n)=Θ (f(n))

In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis for many recurrence relations that occur in the analysis of divide-and-conquer algorithms. The approach was first presented by Jon Bentley, Dorothea Blostein (née Haken), and James B. Saxe in 1980, where it was described as a "unifying method" for solving such recurrences. The name "master theorem" was popularized by the widely used algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.

Not all recurrence relations can be solved by this theorem; its generalizations include the Akra–Bazzi method.

Introduction

• Consider a problem that can be solved using a recursive algorithm such as the following:
• procedure p(input x of size n):
• if n < some constant k:
• Solve x directly without recursion
• else:
• Create a subproblems of x, each having size n/b
• Call procedure p recursively on each subproblem
• Combine the results from the subproblems

The above algorithm divides the problem into a number (a) of subproblems recursively, each subproblem being of size n/b. The factor by which the size of subproblems is reduced (b) need not, in general, be the same as the number of subproblems (a). Its solution tree has a node for each recursive call, with the children of that node being the other calls made from that call. The leaves of the tree are the base cases of the recursion, the subproblems (of size less than k) that do not recurse. The above example would have a child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem n passed to that instance of the recursive call and given by f(n). The total amount of work done by the entire algorithm is the sum of the work performed by all the nodes in the tree.

The runtime of an algorithm such as the p above on an input of size n, usually denoted T(n), can be expressed by the recurrence relation T(n)=a T(n/b)+f(n),

where f(n) is the time to create the subproblems and combine their results in the above procedure. This equation can be successively substituted into itself and expanded to obtain an expression for the total amount of work done.

Generic form

The master theorem always yields asymptotically tight bounds to recurrences from divide and conquer algorithms that partition an input into smaller subproblems of equal sizes, solve the subproblems recursively, and then combine the subproblem solutions to give a solution to the original problem. The time for such an algorithm can be expressed by adding the work that they perform at the top level of their recursion (to divide the problems into subproblems and then combine the subproblem solutions) together with the time made in the recursive calls of the algorithm. If T(n) denotes the total time for the algorithm on an input of size n, and f(n) denotes the amount of time taken at the top level of the recurrence then the time can be expressed by a recurrence relation that takes the form: T(n)=a T (n/b)+f(n)

Here n is the size of an input problem, a is the number of subproblems in the recursion, and b is the factor by which the subproblem size is reduced in each recursive call ( b>1). Crucially, a and b must not depend on n. The theorem below also assumes that, as a base case for the recurrence, T(n)=Θ (1) when n is less than some bound κ >0, the smallest input size that will lead to a recursive call.

Recurrences of this form often satisfy one of the three following regimes, based on how the work to split/recombine the problem f(n) relates to the critical exponent c_(crit)=log _(b)a. (The table below uses standard big O notation).

Inadmissible equations

The following equations cannot be solved using the master theorem: T(n)=2ⁿT(n/2)+nⁿ

a is not a constant; the number of subproblems should be fixed T(n)=2T(n/2)+n/(log n)

non-polynomial difference between f(n) and n^(l)og _(b)a (see below; extended version applies) T(n)=64T(n/8)-n²log n

f(n), which is the combination time, is not positive T(n)=T(n/2)+n(2-cos n)

case 3 but regularity violation.

In the second inadmissible example above, the difference between f(n) and n^(l)og _(b)a can be expressed with the ratio （公式略）. It is clear that 1/(log n)<n^(ε) for any constant ε >0. Therefore, the difference is not polynomial and the basic form of the Master Theorem does not apply. The extended form (case 2b) does apply, giving the solution T(n)=Θ (nlog log n).