LEC ALGO 3

General recursion trees

Refer @ericksonAlgorithms2019 [p. 32]

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

Let $f(n)=n^d$. Time spent doing non recursive work is given by

$$n^d+a{\left(\frac{n}{b}\right)}^d+a^2{\left(\frac{n}{b^2}\right)}^d+\cdots +a^{{\log }_{b}n}{\left(\frac{n}{b^{{\log }_{b}n}}\right)}^d$$

The leaves take $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ time. Thus, total time is given by

$$\begin{array}{r}{n}^{{\log }_{b}a}+\frac{n^{{\log }_{b}a}-n^d{b}^d}{\left(\frac{a}{b^d}-1\right)b^d}\end{array}$$

If $\frac{a}{b^d}>1$, then $T(n)=O(n^{{\log }_{b}a})$. If $\frac{a}{b^d}<1$, then $T(n)=O(n^d)$. If $\left(\frac{a}{b^d}\right)=1$, then $T(n)=O(n^d\log n)$.

---

Divide and conquer algorithms

Fast integer multiplication