# Master Theorem

## March 12, 2021 • Read: 1730 • 算法 • 阅读设置

#### Master Theorem

$$T(n) = aT(\frac{n}{b})+f(n)$$

where $a≥1,b≥1$ be constant and $f(n)$ be a function

Let $T(n)$ is defined on non-negative integers by the recurrence

• $n$ is the size of the problem
• $a$ is the number of sub problems in the recursion
• $\frac{n}{b}$ is the size of each sub problem (Here it is assumed that all sub problems are essentially the same size)
• $f(n)$ is the time to create the sub problems and combine their results in the above procedure

There are following three cases:

1. If $f(n)=\Theta(n^c)$ where $c < log_ba$ then $\color{red}{T(n)=\Theta(n^{log_ba})}$
2. If $f(n)=\Theta(n^c)$ where $c=log_ba$ then $\color{red}{T(n)=\Theta(n^clogn)}$
3. If $f(n)=\Theta(n^c)$ where $c>log_ba$ then $\color{red}{T(n)=\Theta(f(n))}$

#### Indamissible equations

$$T(n)=\color{red}{2^n}T(\frac{n}{2}) + n$$

$a$ is not constant. The number of subproblems should be fixed

$$T(n)=\color{red}{0.5}{T(\frac{n}{2})+n}$$

$a< 1$. Can't have less than 1 subproblems

$$T(n)=16T(\frac{n}{2})\color{red}{-n^2}$$

$f(n)$ which is the combination time is not positive