Neocortex 🧠


Search IconIcon to open search

Master Theorem

Last updated Jan 29, 2023 Edit Source

The master theorem is used to calculate the Big-Oh Complexity of recurrence equations of the form:

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

Where $a \geq 1$ and $b \geq 1$ and $f(n)$ is an asymptotically positive function.

It is important to note that $\frac{n}{b}$ is not always an integer. This is why it is usually in form $\lceil \frac{n}{b} \rceil$ (the ceil function). For notational ease, we will be using the notation without brackets in this note.

It can be used on three cases:

  1. $f(n)= O(n^{log_b{a-\epsilon}})$ (notes/Big-Oh Notation), where $\epsilon > 0$. $T(n) = \Theta(n^{log_ba})$
  2. $f(n)= \Theta(n^{log_b{a}})$ (notes/Big-Theta Notation), then $T(n) = \Theta(n^{log_ba}log n)$
  3. $f(n)= \Omega(n^{log_b{a-\epsilon}})$ (notes/Big-Omega Notation), where $\epsilon > 0$. $T(n) = \Theta(f(n))$

Interactive Graph