Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Master theorem (analysis of algorithms)
Summary
In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in the analysis of many 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 with the use of this theorem; its generalizations include the Akra–Bazzi method.
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 n/b. 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 . 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 , can be expressed by the recurrence relation
where 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.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.