↑ arvau

Wikipedia / Master theorem (analysis of algorithms)

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 algorithmss. 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 () of subproblems recursively, each subproblem being of size . The factor by which the size of subproblems is reduced () need not, in general, be the same as the number of subproblems (). 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 child nodes at each non-leaf node. Each node does an amount of work that corresponds to the size of the subproblem . 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 above on an input of size , can be expressed by the recurrence relation

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. The master theorem allows many recurrence relations of this form to be converted to Θ-notation directly, without doing an expansion of the recursive relation.

Generic form

The master theorem always yields asymptotically tight bounds to recurrences from divide and conquer algorithms 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:

, the smallest input size that will lead to a recursive call.

relates to the critical exponent. (The table below uses standard big O notation.

:

Examples

Case 1 example

As one can see from the formula above:

  1. , so

Next, we see if we satisfy the case 1 condition:

  1. .

It follows from the first case of the master theorem that

).

Case 2 example

As we can see in the formula above the variables get the following values:

Next, we see if we satisfy the case 2 condition:

  1. are equal

So it follows from the second case of the master theorem:

.

).

Case 3 example

As we can see in the formula above the variables get the following values:

Next, we see if we satisfy the case 3 condition:

The regularity condition also holds:

So it follows from the third case of the master theorem:

of the original formula.

.)

Inadmissible equations

The following equations cannot be solved using the master theorem:

  1. a is not a constant; the number of subproblems should be fixed

  2. (see below; extended version applies)

  3. , which is the combination time, is not positive

  4. case 3 but regularity violation.

.

Application to common algorithms

See also

Notes

References