The textbook presents Karatsuba's algorithm for multiplying large integers, which has this recursively defined running time:
\(T(1) = c\)
\(T(n) = 3T(n/2) + O(n)\)
Here is a more detailed presentation of how to use a recursion tree to figure out that its running time is \(O(n^{\log_2 3})\). In this case, we're looking only for a big-O answer, not an exact closed form. So we will cut a few corners.
The tree has 3-way branching and the problem size is reduced by a factor of 2 at each level. So it looks like this:
The height is determined by the reduction in problem size, so it's \(log_2 n\). The number of leaves is the branching factor (3) to the power of the height. So there are \(3^{\log_2 n}\) leaves. Using the change of base formula gives us
\(3^{\log_2 n } = 3^{\log_3 n \cdot \log_2 3} = n^{\log_2 3}\) leaves
Each leaf contains constant work (c). So the work at the leaves is \(cn^{\log_2 3}\). But we can ignore constant multipliers because we only care about the big-O answer.
Now let's look at the internal levels. The kth level of the tree contains \(3^k\) nodes, each containing \(n\frac{1}{2^k}\) work. So each level contains \(n(\frac{3}{2})^k\) work.
The internal levels run from \(k=0\) to \(k=\log_2 n -1\). So the work at all internal levels is:
\(\sum_{k=0}^{\log_2 n -1} n(\frac{3}{2})^k \ \ = \ \ n \sum_{k=0}^{\log_2 n -1} (\frac{3}{2})^k\)
Remember the general formula for the closed form of a geometric series: \(\sum_{k=0}^{n-1} r^k = \frac{r^n -1}{r -1}\). In this case \(r = \frac{3}{2}\).
\(\sum_{k=0}^{\log_2 n -1} n(\frac{3}{2})^k \ \ = \ \ n \sum_{k=0}^{\log_2 n -1} (\frac{3}{2})^k \ \ = n((\frac{3}{2})^{\log_2 n} - 1)(\frac{1}{3/2 - 1}) \)
Ignoring the constant multiplier \((\frac{1}{3/2 - 1})\) gives us \(n((\frac{3}{2})^{\log_2 n} - 1)\). The dominant term of this is \(n(\frac{3}{2})^{\log_2 n}\).
Let's simplify this.
\(n(\frac{3}{2})^{\log_2 n}\ \ =\ \ n(\frac{3^{\log_2 n}}{2^{\log_2 n}}) \ \ =\ \ n(\frac{3^{\log_2 n}}{n}) \ \ =\ \ 3^{\log_2 n}\).
We just saw that \(3^{\log_2 n}\) is equal to \(n^{\log_2 3}\).
So the work at the leaf level and the sum of the non-leaf levels are both \(O(n^{\log_2 3})\).