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

Archives Tip
QR Code for this page
Tipping QR Code