Zhancun Mu

I am a student at PKU and here is my blog.

1 minute read

Video Link

Asymptotic notation

$f(n)=O(g(n))$ means there are consts $C>0, n_{0}>0$ such that $0 \leqslant f(n) \leqslant Cg(n)$ for all $n \geqslant n_{0}$.

Macro convention: A set in a formula represents an anonymous fucntion in that set, e.g $f(n)=n^3+O(n^{2})$.

$\Omega(g(n))$ = { $f(n):$ there exists consts $c>0, n_{0}>0$ such that $0 \leqslant cg(n) \leqslant f(n), \forall n\geqslant n_{0}$ }

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

$o$ and $w$ notation: $\forall c>0 , \exists n_{0}>0,\dots$

Solving Recurrences

Substitution Method:

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

Ex: \(T(n)=4T(\frac{n}{2})+n,T(1)=\Theta(1)\)

  1. Guess $T(n)=O(n^3)$
  2. Assume $T(k) \leqslant ck^3$ for $k \in \mathbb{N}$
  3. \(T(n)=4T\left( \frac{n}{2} \right)+ n \leqslant 4c\left( \frac{n}{2} \right)^3+n = \frac{c}{2} n^3 + n = cn^3 - \left( \frac{c}{2} n^3 - n\right)\leqslant cn^3\) if $\frac{c}{2}n^3-n\geqslant 0$, e.g. $c\geqslant 1,n\geqslant 1$

Prove it’s $O(n^2)$:

  1. Assume $T(k) \leqslant ck^2$
  2. \[T(n) =4T\left( \frac{n}{2} \right)+n\leqslant cn^2+n\]

    Maybe can assume

    \[T(k)\leqslant c_{1} k^2 - c_{2} k\] \[\begin{align} T(n) &= 4T\left( \frac{n}{2} \right)+n \newline &= 4\left( c_{1}\left( \frac{n}{2} \right)^2-c_{2}\left( \frac{n}{2} \right) \right)+n \newline &= c_{1}n^2+(1-2c_{2})n \newline &= c_{1}n^2-c_{2}n-(c_{2}-1)n \newline &\leqslant c_{1}n^2-c_{2}n \quad \text{if} \quad c_{2}\geqslant 1 \end{align}\]

Recursion-tree Method:

Ex. $T(n)=T\left( \frac{n}{4} \right)+T(\frac{n}{2})+n^2$

recursion-tree

compute level by level:

\[T(n)\leqslant \sum_{i=0}^{\infty}\left( \frac{5}{16} \right)^i n^2 < 2n^2 = O(n^2)\]

Master Method: applies to recurrences of the form $T(n)=aT(\frac{n}{b})+f(n)$, where $a > 0,b\geqslant 1,f(n)$ is asymptoticly positive.

compare $f(n)$ with $n^{\log_{b}a}$:

  1. $f(n)=O(n^{\log_{b}a-\epsilon})$ for some $\epsilon > 0$. $=> T(n)=\Theta (n^{\log_{b}a})$.
  2. $f(n)=\Theta(n^{\log_{b}a}\lg^k n)$ for some $k\geqslant 0$ .$\implies T(n)=\Theta(n^{\log_{b}a}\lg^{k+1}n)$.
  3. $f(n)=\Omega (n^{\log_{b}a+\epsilon})$ for some $\epsilon>0$, and $af(\frac{n}{b})<(1-\epsilon’)f(n)$ for some $\epsilon’ >0$. $\implies T(n)=\Theta(f(n))$.

Ex. $T(n)=4T(\frac{n}{2})+n$. $\implies$ case 1: $T(n)=\Theta(n^2)$.

Ex. $T(n)=4T(\frac{n}{2})+n^2$. $\implies$ case 2: $T(n)=\Theta(n^2 \lg n)$.

Ex. $T(n)=4T(\frac{n}{2})+n^3$. $\implies$ case 3: $T(n)=\Theta(n^3)$.

Ex. $T(n)=4T\left( \frac{n}{2} \right)+\frac{n^2}{\log n}$. master method does not apply.

Proof of sketch/intuition:

draw the recursion-tree: height is $\log_{b}n$. bottom level: $a^h=n^{\log_{b}a}$.

case3: costs decrease geometrically $\implies$ domainated by $f(n)$ case1: costs increase geometrically $\implies$ domainated by $\log_{b}a$ case2: each level is roughly the same $\implies$ cost = $f(n) \times h$

Comments

You May Also Enjoy