What is the master theorem (master Theorem)?

Question

What is the master theorem (master Theorem)? What is its importance in the complexity analysis of algorithms?

Answer 1

Division and conquest

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 solved using the algorithm itself that is being defined
• Solutions of smaller instances are combined to produce an original instance solution.

Recurrence

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

Master theorem

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

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

The following Master theorem gives the solution (in asymptotic terms) of all these recurrences.

Theorem: Be it a non-zero natural number, k a natural number, and c a positive real number. Let F be a function that takes natural numbers in positive real numbers and satisfies the recurrence (*) for n = 21, 22, 23, ... Suppose that F is asymptotically nondecreasing, i.e., that there is 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

The Master theorem can be generalized as follows to treat recurrences such as

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

Its 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 limits for the solution.

In other words, Master theorem calculates the resources needed to run a recursive algorithm, such as running time on a computer. The master method uses what is known as notation Big O to describe the asymptotic behavior of functions, i.e., how quickly they grow towards their limit.

Research sources:

• Division and Conquest
• Relatedness
• IME USP
• Master Method of Recurrence