Master Theorem

The Master Theorem provides us a way to solve recurrences of a very special form.
Let $T(n) = aT \left(\dfrac{n}{b} \right) + f \left( n \right)$ , where $a \geq 1, b > 1$ and $f \left( n \right)$ is asymptotically positive (positive for large $n$ as $n$ increases). If $f \left( n \right) \in \Theta \left( n^c \right)$ , then

$T(n) \in \begin{cases} \Theta \left( n^{\log_b a} \right), & \text{if } a > b^c \\ \Theta \left( n^c \log n \right), & \text{if } a = b^c \\ \Theta \left( n^ c \right), & \text{if } a < b^c. \end{cases}$
Let’s demonstrate the Master Theorem using a few examples.
- $T(n) = 4 T \left( \dfrac{n}{2} \right) + n$ .
  
  We see that $a = 4, b = 2, f(n) = n, c = 1$ . The conditions of the Master Theorem are satisfied, so we can use it.
  
  We apply case 1, since $4 > 2^1$ . So $T(n) \in \Theta \left( n^{log_2 4} \right) \Rightarrow T(n) \in \Theta \left( n^2 \right)$ .
- $T(n) = 4 T \left( \dfrac{n}{2} \right) + n^2$ .
  
  We see that $a = 4, b = 2, f(n) = n^2, c = 2$ . The conditions of the Master Theorem are satisfied, so we can use it.
  
  We apply case 2, since $4 = 2^2$ . So $T(n) \in \Theta \left( n^2 \log n \right)$ .
- $T(n) = 4 T \left( \dfrac{n}{2} \right) + n^3$ .
  
  We see that $a = 4, b = 2, f(n) = n^3, c = 3$ . The conditions of the Master Theorem are satisfied, so we can use it.
  
  We apply case 3, since $4 < 2^3$ . So $T(n) \in \Theta \left( n^3 \right)$ .
- $T(n) = 4 T \left( \dfrac{n}{2} \right) + \dfrac{ n^2 }{ \log n }$ .
  
  We see that $a = 4, b = 2, f(n) = \dfrac{ n^2 }{ \log n }$ . The conditions of the Master Theorem are not satisfied, so we cannot proceed to use it.

Master Theorem

Master Theorem

results matching ""

No results matching ""