Recurrences

Recurrences

Asymptotic notation

\(O\)-notation(upper bounds)

\(O(g(n))=\){\(f(n)\): there exist constants \(c>0,n_0>0\) such that \(0≤f(m)≤cg(n)\) for all \(n>n_0\)}

\(\Omega\)-notation(lower bounds)

\(\Omega(g(n))=\){\(f(n):\) there exist constants \(c>0,n_0>0\) such that \(0≤cg(m)≤f(m)\) for all \(n>n_0\)}

\(\Theta\)-notation(tight bounds)

\(\Theta(g(n))=\Omega(g(n)) \cap O(g(n))\)

\(\omicron\)-notation

\(\omicron(g(n))=\){\(f(n)\): for any constants \(c>0\), there is a constant \(n_0>0\) such that \(0≤f(m)≤cg(n)\) for all \(n>n_0\)}

\(\omega\)-notation

\(\omega(g(n))=\){\(f(n)\): for any constants \(c>0\), there is a constant \(n_0>0\) such that \(0≤cg(m)≤f(m)\) for all \(n>n_0\)}

Macro substitution

Convention: A set in a formula represents an anonymous function in the set.

EXAMPLE:

• \(f(n)=n^3 +O(n^2)\) means \(f(n)=n^3+h(n)\) for some \(h(n)\in O(n^2)\).
• \(n^2 +O(n)=O(n^2)\) means \(n^2 +f(n)=h(n)\) for any \(f(n)\in O(n)\) for some \(h(n)\in O(n^2)\).

\(\color{red}{\rule[0pt]{22cm}{0.05em}}\)

Solving recurrences

Substitution method

The most general method:

1. Guess the form of the solution.
2. Verify by induction.
3. Solve for constants.

EXAMPLE: \(T(n)=4T(n/2)+n \quad [T(1)=\Theta(1)]\)

1. Guess \(O(n^3)\).
2. Assume that \(T(k)\le ck^3\) for all \(k<n\)​.
3. Prove \(T(n)\le cn^3\) by induction.

\[ \begin{flalign} &T(n)=4T(n/2)+n& \nonumber\\ &\qquad \le 4c(n/2)^3+n& \nonumber\\ &\qquad=(c/2)n^3+n& \nonumber\\ &\qquad=cn^3-((c/2)n^3-n)\leftarrow desired-residual& \nonumber\\ &\qquad\le cn^3\leftarrow desired& \nonumber\\ &whenever\ (c/2)n^3-n \ge 0, for\ example,if\ c\ge2\ and\ n\ge1& \nonumber\\ \end{flalign} \]

Recursion-tree method

• The method can be unreliable just like any method that uses ellipses(...).
• The method is good for generating guesses for the substitution method.

EXAMPLE: \(T(n)=T(n/4)+T(n/2)+n^2 \quad [T(1)=\Theta(1)]\)

\(T(n)=\Theta(n^2)\)

The master method

The master method applies to recurrences of form: \[ \begin{align*} &T(n)=aT(n/b)+f(n)\\ \text{where }a>1, &b>1, \text{and }f\text{ is asymptotically positive} \end{align*} \]

• \(f(n)=O(n^{\log_ba-\xi} )\) for some constant \(\xi>0\). \(f(n)\) grows polynomially slower than \(n^{\log_ba}\)(by an \(n^\xi\) factor).

  Solution: \(T(n)=\Theta(n^{\log_ba})\).

• \(f(n)=\Theta(n^{\log_bx}\lg^ka )\) for some constant \(k\ge0\). \(f(n)\) and \(n^{\log_ba}\) grow at similar rates.

  Solution: \(T(n)=\Theta(n^{\log_ba}\lg^{k+1}n)\).

• \(f(n)=\Omega(n^{\log_ba+\xi} )\) for some constant \(\xi>0\). \(f(n)\) grows polynomially faster than \(n^{\log_ba}\)(by an \(n^\xi\)​ factor) and \(f(n)\) satisfies the regularity condition that \(af(n/b)\le cf(n)\) for some constant \(c<1\).

  Solution: \(T(n)=\Theta(f(n))\).

EXAMPLE:

1. \[ \begin{align} &T(n)=4T(n/2)+n& \nonumber\\ a=4, &b=2 \Rightarrow n^{\log_ba}=n^2;f(n)=n& \nonumber\\ \text{CASE }&1: f(n)=O(n^{2-\xi})\quad for\ \xi=1& \nonumber\\ \therefore &T(n)=\Theta(n^2)& \nonumber\\ \end{align} \]

2. \[ \begin{align} &T(n)=4T(n/2)+n^2& \nonumber\\ a=4, &b=2 \Rightarrow n^{\log_ba}=n^2;f(n)=n^2& \nonumber\\ CASE\ &2: f(n)=\Theta(n^2\lg^0n)\quad k=0& \nonumber\\ \therefore &T(n)=\Theta(n^2\lg n)& \nonumber\\ \end{align} \]

3. \[ \begin{align} &T(n)=4T(n/2)+n^3& \nonumber\\ a=4, &b=2 \Rightarrow n^{\log_ba}=n^2;f(n)=n^3& \nonumber\\ CASE\ &3: f(n)=\Omega(n^{2-\xi})\quad for\ \xi=1& \nonumber\\ and\ 4(n/2)^3&\le cn(reg. cond. )\quad for\ c=1/2& \nonumber\\ \therefore &T(n)=\Theta(n^3)& \nonumber\\ \end{align} \]

4. \[ \begin{align} &T(n)=4T(n/2)+n^2/\lg n& \nonumber\\ a=4, &b=2 \Rightarrow n^{\log_ba}=n^2;f(n)=n^2/\lg n& \nonumber\\ \end{align} \] Master method does not apply. In particular, for every constant \(\xi>0,\) we have \(n^\xi = \omega(\lg n)\).

Idea of master theorem

CASE 1: The weight increases geometrically from the root to the leaves. The leaves hold a constant fraction of the total weight.

\(\therefore T(n)=\Theta(n^{\log_ba})\)

CASE 2: \((k=0)\)The weight is approximately the same on each of the \(log_bn\) levels.

\(\therefore T(n)=\Theta(n^{\log_ba}\lg n)\)

CASE 3: The weight decreases geometrically from the root to the leaves. The root holds a constant fraction of the total weight.

\(\therefore T(n)=\Theta(f(n))\)