Divide and conquer

Idea: divide the problem into several (equal) parts $\to$ (recursively) conquer/solve each of the sub problems $\to$ combine sub problem solutions

Substitution method

Guess the solution, then find the constants using induction
Prove solution validity with induction

Example

$T(n)=2T(\frac{n}{2})+nlogn$
Assume: $T(n)=O(nlogn)$
Prove: $T(n)\le c\ast nlogn;c>0,n>n_0$
Inductive assumption: $T(n)\le c\ast 2\ast \frac{n}{2}log\frac{n}{2}+n=...=cn\ast logn-n(1-c)$
Base case: $T(1)$ not, but $T(2)$ yes

Recursive tree

Draw recursive tree, then sum complexity level-wise and altogether
Prove solution validity with induction

Example

$T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+\Theta (n)$
Assume: $T(n)\le T(\frac{n}{3})+T(\frac{2n}{3})+cn$, $T(1)=\Theta (1)$
Draw tree:

Proof by induction: $T(n)\le d\ast nlogn$

Master theorem

1. Get $a$, $b$ and $f(n)$ from:

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

2. Calculate $n^{lo{g}_{b}a}$
3. Use it to determine the asymptotic bounds of $T(n)$:
   Less / more leafs in recursion tree $\to$ peak dominates (1. rule) / bottom dominates (3. rule)

$$\begin{array}{rl}f(n)=O(n^{lo{g}_{b}a-ϵ})& ⟹T(n)=\Theta (n^{lo{g}_{b}a})\\ f(n)=\Theta (n^{lo{g}_{b}a-ϵ})& ⟹T(n)=\Theta (n^{lo{g}_{b}a}logn)\\ f(n)=\Omega (n^{lo{g}_{b}a+ϵ})& ⟹T(n)=\Theta (f(n))\end{array}$$

Example

$T(n)=3T(\frac{n}{4})+nlogn$ $\to$ $a=3$, $b=4$, $f(n)=nlogn$
$n^{lo{g}_{b}a}=n^{lo{g}_{4}3}\in (0,1)$
$nlogn\ne O(n^{lo{g}_{4}3-ϵ})$, $nlogn\ne \Theta (n^{lo{g}_{4}3-ϵ})$
$nlogn=\Omega (n^{lo{g}_{4}3+ϵ})$ $\to$ $T(n)=\Theta (nlogn)$

Akra-Bazzi theorem

1. Get all $a_i$, $b_i$ and $f(n)$ which must be polinomially limited
2. Calculate $p$ in $\sum a_i\ast (b_i{)}^p=1$
3. Use it to determine the asymptotic bounds of $T(n)$:

$$T(x)=\Theta (x^p(1+{\int }_1^x\frac{f(u)}{u^{p+1}}du))$$

Example

$T(n)=T(\frac{3n}{4})+T(\frac{n}{4})+n$ $\to$ $a_1=1$, $b_1=\frac{3}{4}$, $a_2=1$, $b_2=\frac{1}{4}$, $f(n)=nlogn$
$1\ast (\frac{3}{4}{)}^p+1\ast (\frac{1}{4}{)}^p=1$ $\to$ $p=1$
$T(x)=...=\Theta (xlnx)$

Solving linear recurrances with annihilators

Linear reccurance: $T(n)$ is a linear combination of nearby values $T(n-1)$, $T(n-2)$, …
Operator: higher order function, taking other functions as arguments (eg. integral, differential, … )

Operator	Definition
Addition	$(f+g)(n)=f(n)+g(n)$
Substraction	$(f-g)(n)=f(n)-g(n)$
Multiplication	$(\alpha \ast f)(n)=\alpha \ast (f(n))$
Shift	$Ef(n)=f(n+1)$
$k$-fold shift	$E^{k}f(n)=f(n+k)$
Composition	$(X+Y)f=Xf+Yf$ $(X-Y)f=Xf-Yf$ $XYf=X(Yf)=Y(Xf)$
Distribution	$X(f+g)=Xf+Xg$
Annihilator: nontrivial operator transforming function to 0, every polinomial/exponential function has a unique minimal annihilator

Operator	Function annihilated
$E-a$	$\alpha \ast a^n$
$(E-a_0)(E-a_1)...(E-a_k)$	${\sum }_{i=0}^k\alpha \ast a_i^n$

• $X$ annihilates $f$ $⟹$ $X$ annihilates $Ef$
• $X$ annihilates $f$ $⟹$ $X$ annihilates $\alpha f$ for any constant $\alpha$
• $X$ annihilates $f$ and $g$ $⟹$ $X$ annihilates $f\pm g$
• $X$ annihilates $f$ and $Y$ annihilates $g$ $⟹$ $XY$ annihilates $f\pm g$

Annihilating recurrances:

1. Write recurrance in operator form
2. Extract an annihilator for the recurrance
3. Factor the annihilator (if necessary and possible)
4. Extract the generic solution from the annihilator
5. Solve for coefficients using the base cases (if known)

Example

$\tau (n)=5\tau (n-1);\tau (0)=3$
$\tau (n)-5\tau (n-1)=0$
$\tau (n+1)-5\tau (n)=0$
$E\tau -5\tau =0$
$(E-5)\tau (n)$ $\to$ $\tau (n)=\alpha \ast 5^n$ … generic solution
$\tau (0)=3⟹3=\alpha \ast 5^0⟹\alpha =3$ $\to$ $\tau (n)=3\ast 5^n$