# Recurrence tree method

We consider the following example: suppose the recurrence $T(n) = 3 T\left( \left \lfloor \frac{n}{4} \right \rfloor \right) + cn^2$. We can neglect the floor and ceiling functions, hence will replace this recurrence by:
$$T(n) = 3 T\left( \frac{n}{4} \right) + cn^2$$
Assume further, for simplicity, that $n$ is divisible by $4$. The calls are reflected in the following **recurrence tree**:

How can this be used to find an upper bound for $T(n)$?

1. The height of the tree is $\log_4 n$. The leaves are labeled $T(1)$, and there exists $3^{\log_4 n}$ many of such. We can use the following logarithm law to rewrite this as a power of $n$:
$$a^{\log_b c} = c^{\log_b a}$$
Thus, $3^{\log_4 n} = n^{\log_4 3}$.

2. The costs at the various levels of the trees are as follows:

* Root level $i = 0$: $\quad$ $cn^2$
* Leaf level $i = \log_4 n$: $\quad$ $\Theta(n^{\log_4 3})$
* Intermediate levels $1 \leq i \leq \log_4 n - 1$: $\quad$ $3^i c \left( \frac{n}{4^i}\right)^2 = \left( \frac{3}{16}\right)^i cn^2$

Summing up, the recurrence then unfolds to:
$$T(n) = \sum_{i=0}^{\log_4 n - 1} \left( \frac{3}{16}\right)^i cn^2 + \Theta(n^{\log_4 3}) = cn^2 + 3c \left( \frac{n}{4}\right)^2 + 9c \left( \frac{n}{16}\right)^2 + \ldots + \Theta(n^{\log_4 3})$$

This contains a [geometric sum](https://en.wikipedia.org/wiki/Geometric_series#Definition:_finite_geometric_series):

$$\sum_{i=0}^n q^i = \frac{1-q^{n+1}}{1-q}$$

Thus:

$$\sum_{i=0}^{\log_4 n - 1} \left( \frac{3}{16}\right)^i = \frac{1- \left( \frac{3}{16}\right)^{\log_4n}}{1-\frac{3}{16}},$$
so that:
$$T(n) = \left( \frac{1- \left( \frac{3}{16}\right)^{\log_4n}}{1-\frac{3}{16}} \right) cn^2 + \Theta(n^{\log_4 3}) $$
In some cases, this step might yield a transparent result, but ours looks messy here.

3.
We can use the **infinite geometric series** as an upper bound:

$$\begin{align*}
T(n) & = \sum_{i=0}^{\log_4 n - 1} \left( \frac{3}{16}\right)^i cn^2 + \Theta(n^{\log_4 3}) \\
& \leq \sum_{i=0}^{\infty} \left( \frac{3}{16}\right)^i cn^2 + \Theta(n^{\log_4 3}) \\
& = cn^2 \sum_{i=0}^{\infty} \left( \frac{3}{16}\right)^i + \Theta(n^{\log_4 3})
\end{align*}$$

This [geometric series](https://en.wikipedia.org/wiki/Geometric_series#Infinite_geometric_series_and_convergence) converges:

For $|q| < 1$ we have that
$$\sum_{i = 0}^\infty q^i = \frac{1}{1-q}.$$

Thus:

$$\begin{align}
T(n) & = \sum_{i=0}^{\log_4 n - 1} \left( \frac{3}{16}\right)^i cn^2 + \Theta(n^{\log_4 3}) \\
& \leq \sum_{i=0}^{\infty} \left( \frac{3}{16}\right)^i cn^2 + \Theta(n^{\log_4 3}) \\
& = cn^2 \sum_{i=0}^{\infty} \left( \frac{3}{16}\right)^i + \Theta(n^{\log_4 3}) \\
& = \frac{cn^2}{1 - \frac{3}{16}} + \Theta(n^{\log_4 3}) \\
& = \frac{16}{13}cn^2 + \Theta(n^{\log_4 3}) \\
& \in \mathcal O(n^2)
\end{align}$$

:::success
**Example.**
Let $T(n) = 3 T\left(\lfloor \frac{n}{2}\rfloor\right) + n$. We want to solve this recurrence. First, we can neglegt the floor function, thus assume $T(n) = 3 T\left(\frac{n}{2}\right) + n$. Furthermore, we assume $n$ to be divisible by $2$. The first levels of the tree are given by:
The depth of the tree is $\log_2 n$, with $3^{\log_2 n} = n^{\log_2 3}$ many leaves, each taking $T(1)$ many steps. Thus, we obtain:
$$\begin{align*}
T(n) & = \sum_{i = 0}^{\log_2 n} \left(\frac{3}{2}\right)^i n \\
& = n \left( \frac{1-\left(\frac{3}{2}\right)^{\log_2n+1}}{1-\frac{3}{2}}\right) \\
& = \frac{n \left( 2^{\log_2 n + 1} - 3^{\log_2 n +1} \right)}{\underbrace{2^{\log_2 n + 1}}_{=2n} \left( 1 - \frac{3}{2}\right)} \\
& = \frac{n \left(2n - 3^{\log_2 n + 1}\right)}{2n\left(1-\frac{3}{2}\right)} \\
& = (-1) \cdot \left( 2n - 3^{\log_2 n + 1} \right) \\
& = 3 \cdot 3^{\log_2n} - 2n \\
& \leq 3 \cdot 3^{\log_2n} = 3 n^{\log_2 3} \in \mathcal O(n^{\log_2 3})
\end{align*}$$
:::

:::info
**Remark.** We might also consider more sophisticated recurrence conditions where the steps might take different amounts of time, such as
$$T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + cn$$
for some $c > 0$.

The recurrence tree looks as follows:

One could analyze this more precisely, but it's enough to consider the tree we would get by replacing $T\left(\frac{n}{3}\right)$ by $T\left(\frac{2n}{3}\right)$.

Then, we would get a binary tree of height $\log_{\frac{3}{2}}n$. The cost for each level is at most $\Theta(n^{\log_{\frac{3}{2}} 2})$. Since $\log_{\frac{3}{2}}2 > 1$, the cost is in $\omega(n \log_2 n)$. But since our tree actually has fewer leaves, we could guess that $\mathcal O(n \log_2 n)$ is an upper bound which one can show to be true by induction.
:::

:::warning
**Exercises.**
In Cormen et al., solve Exercises 4.4-2 and 4.4-5 using recurrence trees. Prove your results using induction.
:::