blog

Introduction

The master mwthod provides a 'cookbook' method for solving recurrences of the form

$\Gamma(n) = a\Gamma(\frac{n}{b}) + \hat{a}(n)$

where $a\geq1$ and $b\geq1$ are constants and $\hat{a}(n)$ is an asymptotically positive function. The master method requires memorization of three cases, but then the solution of many recurrences can be determined quite easily, often without pencil and paper

the master theorem

The master theorem method depends on the following theorem.
Theorem 1.1
Let $a\geq1$ and $b\geq1$ be constants, let $\hat{a}(n)$ be a function, and let $\Gamma(n)$ be defined on the nonnegative integers ny the recurrence

$\Gamma(n) = a\Gamma(\frac{n}{b}) + \hat{a}(n)$

where we interpret $frac{n}{b}$ to be mean either $\left \lfloor \frac{n}{b} \right \rfloor$ or $\left \lceil \frac{n}{b} \right \rceil$. THen $\Gamma(n)$ can be bounded as asymptotically as follow:

1. if $\hat{a}(n) = O(n^{log_{b}^{a}-\epsilon})$ for some constants $\epsilon >0$, the $\Gamma(n) = \Theta(n^{log_{b}^{a}})$
2. if $\hat{a}(n) = \Theta(n^{log_{b}^{a]}})$, the $\Gamma(n) = \Theta(n^{log_{b}{a}} * lgn)$
3. if $\hat{a}(n) = \Omega(n*log_{b}{a}+\epsilon)$ for some constant $\epsilon > 0$, and if $a\hat{a}(\frac{n}{b}) \leq c\hat{a}(n)$ for some constant $c \leq 1$ and all sufficiently large n, then $\Gamma(n) = \Theta(\hat{a}(n))$

Before applying the master theorem to some examples, let's spend a moment trying to understand what is says. In each od the cases, we are comparing the function $\hat{a}(n)$ with the function $n^{log_{b}{a}}$, Intutively, the solution to the recurrence is determined by the larger of two functions. If, as in case 1, the function $n^{log_{b}{a}}$ is the larger, then the solution is $\Gamma(n) = \Theta(\hat{a}(n^{log_{b}{a}}))$. If, as in case 3, the function $\hat{a}(n)$ is larger, then the solution is $\Gamma(n) = \Theta(\hat{a}(n))$. If, as in case 2, t he function are the same size, we multiply by alogarithmic factor, and the solution is $\Gamma(n) = \Theta(n^{log_{b}{a}}) = \Theta(\hat{a}(n) * lgn)$.

Beyond this function, there are some technicalities that must be understood. In the first caee, not only must $\hat{a}(n)$ be smaller than $n^{log_{b}{a}}$, it must be polynomially smaller. That is, $\hat{a}(n)$ must be asymptotically smaller than $n^{log_{b}{a}}$ by a factor of $\epsilon$ for some $\epsilon > 0$. In the third case, not only must $\hat{a}(n)$ be larger than $n^{log_{b}{a}}$, it must be polynomially larger and in addition satisfy the "regularity" condition that $a\hat{a}(\frac{n}{b}) \leq c\hat{a}(n)$. This condition is satisfied by most of the polynomially bounded functions that we shall encounter.

It is important to realize that the three cases do not cover all the possibilities for $\hat{a}(n)$. There is a gap between cases 1 and 2 when $\hat{a}(n)$ is smaller than $n^{log_{b}{a}}$ but not polynomially smaller. Similary, there is a gap between case 2 and 3 when $\hat{a}(n)$ is larger than $n^{log_{b}{a}}$ but not polynonially larger. If the function $\hat{a}(n)$ falls into one of these gaps, or if the regularity condition in case 3 fails to hold, the master theorem cannot used to solve the recurrence.

zero-centered is an important operation for data before using PCA, as it will extract the matric feature vector