Divide and Conquer Algorithms

Quick reference for three divide and conquer staples, with proof sketches.

Master Theorem

Given any recurrence of the form $T(n)=aT(\frac{n}{b})+c{n}^k$ for all $n>b$, we have:

• If $a>b^k$, then $T(n)=\Theta (n^{{\log }_{b}a})$
• If $a<b^k$, then $T(n)=\Theta (n^k)$
• If $a=b^k$, then $T(n)=\Theta (n^k\log n)$

Root Finding

Given a continuous function $f$ and two points $a<b$ such that $f(a)\cdot f(b)<0$, there exists a root of $f$ in the interval $[a,b]$ by the intermediate value theorem. Since said root may be irrational, we aim to approximate it with an arbitrary precision $ϵ$.

• Algorithm: $Bisect(a,b,ϵ)$, assuming the orientation $f(a)\le 0\le f(b)$ (flip the comparison otherwise)
  • If $b-a<ϵ$, $a$ is a suitable approximation
  • Otherwise, calculate the midpoint $m=(a+b)/2$
  • If $f(m)\le 0$ then return $Bisect(m,b,ϵ)$
  • else return $Bisect(a,m,ϵ)$
• Time: $T(n)=T(\frac{n}{2})+O(1)=O(\log (\frac{b-a}{ϵ}))$
• Proof:
  • $P(k)=$ For any $a,b$ such that $kϵ\le |a-b|\le (k+1)ϵ$, if $f(a)f(b)\le 0$, then we find an $ϵ$ approx to a root using $\log k$ queries to $f$.
  • $P(1)$: Output $a+ϵ$, since the whole interval is at most $ϵ$. This requires $0$ calls to $f$.
  • Suppose $P(k)$ and consider an arbitrary $a$, $b$ s.t. $2kϵ\le |a-b|\le (2k+1)ϵ$.
  • If $f(a+kϵ)=0$, output $a+kϵ$.
  • If $f(a)f(a+kϵ)<0$, solve on the interval $[a,a+kϵ]$. By I.H. this takes at most $\log (k)$ queries of $f$.
  • Otherwise, we have $f(b)f(a+kϵ)<0$, since $f(a)f(b)<0$ and $f(a)f(a+kϵ)\ge 0$. Solve the interval $[a+kϵ,b]$.
  • In any case, we used at most $\log (k)+1=\log (2k)$ queries to $f$.

kth Smallest Element

• Algorithm: $f(S\in {\mathbb{R}}^n,k\in \mathbb{R})$
  • Select an approximate median element $w$ using the median of the $\frac{n}{5}$ medians of subarrays of size $5$
  • Partition each element into three sets, $S_{>},S_{<},S_{=}$
  • If $k\le |S_{<}|$, recurse on $f(S_{<},k)$
  • Else, if $k\le |S_{<}|+|S_{=}|$, return $w$
  • Else, recurse on $f(S_{>},k-|S_{<}|-|S_{=}|)$

Related

• Divide and Conquer Examples and Analysis
• Algorithm Efficiency and Asymptotic Notation
• Approximation Algorithms
• Dynamic Programming
• Greedy Algorithms
• Graph Theory
• Interval Scheduling/Partitioning