Recurrence

• $T(n)=2T(n/2+17)+n=O(n\lg n)$

Substitution method

• $T(n)=T(n-1)+n=O(n^2)$ (quick sort worst case (e7.2-1))
• $T(n)=T(n-1)+1=O(n)$ (worst-case of Random in Ramdomized-Quicksort (e7.3-2))
• $T(n)=2T(\lfloor \sqrt{n}\rfloor )+\lg n=\Theta (\lg n\lg \lg n)$ (4.1)
• $T(n)=T(\lceil n/2\rceil )+1=\Theta (\lg n)$ (e4.1-1)

Rucursion-tree method

• dsd

Changing variables

• Given $T(n)=aT(n^{1/2})+{\lg }^{q}n$
• Define: $m=\lg n⟹2^m=n$
• Therefore, $T(2^m)=aT(2^{m/2})+m^q$

Master Theorem

$T(n)=aT(n/b)+f(n)(a\ge 1,b>1)$

1.	$f(n)=O(n^{{\log }_{b}a-ϵ})$ for some constant $ϵ>0$	$T(n)=\Theta (n^{{\log }_{b}a})$
2.	$f(n)=\Theta (n^{{\log }_{b}a})$	$T(n)=\Theta (n^{{\log }_{b}a}\lg n)$
3.	$f(n)=\Omega (n^{{\log }_{b}a+ϵ})$ for some constant $ϵ>0$, and if $af(n/b)\le cf(n)$ for some constant $c<1$ and all sufficiently large $n$	$T(n)=\Theta (f(n))$

2 -

$T(n)=aT(n/b)+\Theta (n^k{\log }^{p}n)$

• Case 1. if ${\log }_{b}a>k$ (that is $a>b^k$), then:
  • $T(n)=\Theta (n^{{\log }_{b}a})$
• Case 2. if ${\log }_{b}a=k$ (that is $a=b^k$), then:
  • (2a) if $p>-1$, then $T(n)=\Theta (n^k{\log }^{(p+1)}n)=\Theta (n^{{\log }_{b}a}{\log }^{(p+1)}n)$
  • (2b) if $p=-1$, then $T(n)=\Theta (n^k\log \log n)=\Theta (n^{{\log }_{b}a}\log \log n)$
  • (2c) if $p<-1$, then $T(n)=\Theta (n^k)=\Theta (n^{{\log }_{b}a})$
• Case 3. if ${\log }_{b}a<k$ (that is $a<b^k$), then:
  • (3a) if $p\ge 0$, then $T(n)=\Theta (n^k{\log }^{p}n)$
  • (3b) if $p<0$, then $T(n)=\Theta (n^k)$

Examples

• Case 1:
  • ($a=4,b=2,k=1,p=0$) $T(n)=4T(n/2)+\Theta (n)=\Theta (n^{{\log }_{2}4})=\Theta (n^2)$
  • ($a=9,b=3,k=1,p=0$) $T(n)=9T(n/3)+n=\Theta (n^{{\log }_{3}9})=\Theta (n^2)$
  • $T(n)=4T(n/2)+\Theta (n)=\Theta (n^2)$
  • $T(n)=2T(n/2)+\Theta (1)=\Theta (n)$ (best-case of Random in Ramdomized-Quicksort (e7.3-2))
  • $T(n)=3T(n/2)+\Theta (n)=O(n^{\lg 3})$
• Case 2:
  • (2a)
    • ($a=1,b=\frac{2}{3},p=0>-1,k=0$) $T(n)=T(2n/3)+\Theta (1)=\Theta (n^{{\log }_{2/3}1}\lg n)=\Theta (n^0\lg n)=\Theta (\lg n)$ (max-heapify)
    • $T(n)=2T(n/2)+\Theta (n)=\Theta (n\lg n)$ (quick-sort best case; merge-sort)
    • $T(n)=T(n/2)+\Theta (1)=O(\lg n)$
• Case 3:
  • (3a)
    • ($a=1,b=2,k=2,p=0$) $T(n)=T(n/2)+n^2=\Theta (n^2{\log }^{0}n)=\Theta (n^2)$
    • ($a=3,b=4,k=1,p=1\ge 0$) $T(n)=3T(n/4)+n\lg n=\Theta (n\lg n)$
    • $T(n)=2T(n/3)+\Theta (n)=\Theta (n)$

• $T(n)\le 2T(n/2)+O(n^d)$
  • if $d=0$ then $T(n)\le 2T(n/2)+O(1)$
    • $T(n)\le \sum _{i=0}^{\log n}{2}^i\cdot O(1)=O(2^{\log n})=O(n)$
    • increasing geometry series, thus, the value of $T(n)$ is dominated by the last level, which is $O(n)$
  • if $d=1$ then $T(n)\le 2T(n/2)+O(n)$
    • $T(n)\le \sum _{i=0}^{\log n}{2}^i\cdot O(n/2^i)=O(n\log n)$
    • (e.g. merge-sort)
    • constant geometry series
    • each level costs $O(n)$
    • there are $\log n$ levels
    • total cost is $O(n\log n)$
  • if $d=2$ then $T(n)\le 2T(n/2)+O(n^2)$
    • $T(n)\le \sum _{i=0}^{\log n}{2}^i\cdot O(n^2/4^i)=O(n^2)\cdot \sum _{i=0}^{\log n}{2}^{-i}=O(n^2)$
    • decreasing geometry series, thus, the value of $T(n)$ is dominated by the first level, which is $O(n^2)$