What is the master theorem?

Division and achievement

The structure of many efficient algorithms follows the paradigm of division and conquest. This paradigm (or algorithm design strategy) consists of the following:

• The given instance of the problem is divided into two or more smaller instances,
• Each smaller instance is resolved using the algorithm being defined itself
• Solutions from smaller instances are combined to produce a solution of the original instance.

Recurrence

It is a mathematical technique that allows to define sequences, sets, operations or even algorithms starting from particular problems for generic problems. That is, by means of a rule one can calculate any term according to the immediate predecessor (s).

Master Theorem

Many of the recurrences that occur in parsing division and conquest algorithms have the form:

F(n)  =  a F(n/2) + cn^k

  

Theorem: Let a nonzero natural number, k be a natural number, and c is a positive real number. Let F be a function that takes natural numbers into positive real numbers and satisfies the recurrence (*) for n = 21, 22, 23, ... Suppose that F is asymptotically non-decreasing, ie that there exists n1 such that F (n) ≤ F (n + 1) for all n ≥ n1. Under these conditions,

     

• if lg a > k then F is in Θ (n ^ lg a),
  
• if lg a = k then F is in Θ (n ^ k lg n),
  
• if lg a < k then F is in Θ (n ^ k).
  

Generalization

F(n)  =  a F(n/b) + cn^k.   

Your Importance (use) *

The Master Theorem allows you a way around this problem by comparing a recursive algorithm with other algorithms, which allows you to estimate the upper and lower bounds for the solution.

In other words, Master Theorem calculates the resources required to run a recursive algorithm, such as runtime on a computer. The master method uses what is known as Big O notation to describe the asymptotic behavior of functions, that is, how quickly they grow toward their limit.

Search sources:

• Division and Conquest
• Recurrence Ratio
• IME USP
• Master Recurrence Method