Master Theorem

Learned in CS341.

The “Master Theorem” provides a formula for the solution for many recurrence relations typically encountered in the analysis of Divide and Conquer algorithms.

Simplified version:

Theorem (Master Theorem)

Suppose that $a\ge 1$ and $b>1$ . Consider the recurrence $T(n)=aT(\frac{n}{b})+\Theta (n^y)$ in a sloppy or exact form. Denote $x={\log }_{b}a$. Then

where $a>0$ and $b>1$ are constants and $f(n)$ is a given “driving” function. It characterizes a divide-and-conquer algorithm that creates $a$ subproblems, each of which is $1/b$ times the size of the original problem, using $f(n)$ time for the divide and combine steps.

Unlike the Recursion-tree method, the master theorem provides bound for recurrences of the form $T(n)=aT(\frac{n}{b})+f(n)$ Need to memorize 3 cases, but then you will easily be able to determine asymptotic bounds for many simple recurrences. We will use it to determine the running time of divide-and-conquer algorithms for the maximum-subarray problem and for matrix multiplication.

Textbook Chapter 4.5 explains it fairly well and provides examples:todo

Related

• Recurrence Relations
• Maximum Subarray
• Median of medians