Recurrence Relations · Application: Divide and Conquer

Lesson 6

Nikolai Chukhin · Alexander S. Kulikov

Now we are ready to prove the theorem about recurrence relations.

Proof. Expand the recurrence relation \(T(n)=cn^{d}+aT(n/b)\): \[\begin{align*}T(n)&=cn^{d}+aT(n/b)\\&=cn^{d}+a(c(n/b)^{d}+aT(n/b^{2}))=cn^{d}+ca(n/b)^{d}+a^{2}T(n/b^{2})=\\&\vdots\\&=cn^{d}+ca(n/b)^{d}+ca^{2}(n/b^{2})^{d}+\dotsb=\\&=\sum_{l=0}^{\log_bn}ca^{l}\left(\frac{n}{b^l}\right)^{d}=\\&=\sum_{l=0}^{\log_bn}a^{l} \cdot c \cdot \frac{n^d}{b^{ld}}=\\&=cn^{d}\sum_{l=0}^{\log_bn}\frac{a^l}{b^{ld}}=\\&=cn^{d}\sum_{l=0}^{\log_bn}\left(\frac{a}{b^{d}}\right)^{l}=\\&=cn^{d}\sum_{l=0}^{\log_bn}\alpha^{l},\end{align*}\] where \(\alpha=\frac{a}{b^d}\). Below, we show a slightly more visual method of deriving this formula. We will then estimate the resulting expression.

The recursion tree of the algorithm is shown below. For each level, the number of problems, their sizes, and the total work performed by the algorithm at that level are displayed.

At each lower level, the size of subproblems decreases by a factor of \(b\), while the number of subproblems increases by a factor of \(a\). At level \(l\), there are \(a^{l}\) tasks of size \(n/b^{l}\), and the total work at this level is \[a^{l} \cdot c \cdot \left( \frac{n}{b^l}\right)^{d} \ .\] Summing over all levels \[l=0,1,\dotsc,\log_{b}n,\] we obtain \(\sum_{l=0}^{\log_bn}ca^{l}\left(\frac{n}{b^l}\right)^{d}\). Thus, it remains to evaluate \(cn^{d}\sum_{l=0}^{\log_bn}\alpha^{l}\).

Consider three cases.

  1. \(a>b^{d}\). Then \[cn^{d}\cdot \left(\frac{a}{b^{d}}\right)^{\log_{b}n}=cn^{d} \cdot \frac{a^{\log_{b}n}}{b^{d\log_{b}n}}= cn^{d}\cdot \frac{n^{\log_{b}a}}{n^d}=c\cdot n^{\log_{b}a}=O(n^{\log_{b}a}) \ .\] (We used the equalities \(a^{\log_{b}n}=n^{\log_{b}a}\) and \(b^{\log_{b}n}=n\).)
  2. \(a=b^{d}\). Then \[cn^{d} \cdot O(\log_{b}n)=O(n^{d}\log n) \ .\] (The logarithm base inside \(O(\cdot)\) can be omitted if it is constant.)
  3. \(a<b^{d}\). Then \[cn^{d}\cdot O(1)=O(n^{d}) \ .\]
◼