1. Introduction

• Implementation of Karatsuba Multiplication in Python

2. Asymptotic Notation

Note: See ‣ for rigorous treatment.

3. D&C Algorithms

4. Master Method

Note: This is a special case of Akra-Bazzi; see‣.

Recursion Trees

Recursion trees give a nice visual intuition into what’s going on with standard D&C recurrences.

From Algorithms (Erickson; 2019), this picture helps build intuition about how to calculate $T(n)$ , which is the sum of all the values in each node of this recursion tree!

$T(n) = rT\left(\frac{n}{c}\right) + f(n)$ gives the D&C recurrence (i.e., $r=a$, $c =b$ when compared to Roughgarden’s formulation above; $d$ from above is the exponent on the bound for the non-recursive work done, i.e., $O(f(n)) = O(n^d)$).

• The root of the recursion tree for $T(n)$ has value $f(n)$ and $r$ children, each of which is the root of a (recursively defined) recursion tree for $T(n/c)$. Equivalently, a recursion tree is a complete $r$-ary tree where each node at depth $d$ contains the value $f(n/c^d)$. (Feel free to assume that $n$ is an integer power of $c$, so that $n/c^d$ is always an integer, although in fact this doesn’t matter.)

• We are interested in $T(n)$, which is the sum of all values of nodes in the recursion tree. Each term in this sum is the level-by-level aggregate:

  $$ T(n) = \sum_{i=0}^{L} r^{i} \cdot f\left( \frac{n}{c^{i}}\right) $$

  In the Roughgarden’s parlance, the summation above is the same as (let $i = j$ and the same variables as mentioned above):

  

  Note: Here, $c$ is just an arbitrary constant (from the runtime of non-recursive work done).

  So, in total, $T(n)$ can be described:

  

  The reason the why the denominator is also raised to the $d$ power:

  

• $L = \log_{c}{n}$ because it’s the depth of the recursion tree after repeatedly dividing the input size $n$ by $c$ until we reach our base case (i.e., assume, for convenience, $n_0 = 1$ such that $n \leq n_{0}$ has $T(n) = 1$; the exact base case doesn’t matter because we’re looking for asymptotic bounds). Repeated division gives $c^{L} = n$.

• The number of leaves in the recursion tree is $r^{L}=r^{\log_{c}{n}}=n^{\log_{c}{r}}$

  • Why we can switch $r$ and $n$?

• Per the Master Method, there are three cases where the level-by-level sum is easy to evaluate (matched to the cases above):

  • [Case 1: all terms in the series are equal, i.e., $r = c^{d}$] This immediately gives $O(f(n) \cdot L) = O(n^d \cdot \log n)$ because their are $L = \log_{c}{n}$ terms and each term is upper-bounded by $f(n)$.
    • Note that $c$ disappears in $O$-notation because any two logarithm functions differ only by a constant factor. **
  • [Case 2: the series decreases exponentially, i.e., $r < c^d$] Every term is a constant factor smaller than the previous term, so the value at the recursion tree’s root dominates: $T(n) = O(f(n)) = O(n^d)$.
    • Note that any decreasing geometric series is [asymptotically] dominated by it’s first term!
  • [Case 3: the series increases exponentially, i.e., $r > c^d$] Every term is a constant factor bigger than the previous term, so the sum is dominated by the number of leaves in the recursion tree: $T(n) = O(n^{log_{c}{r}})$.
    • Note that any increasing geometric series is [asymptotically] dominated by it’s last term!