In the previous post, we learned the Master method and the Akra-Bazzi method to solve the divide and conquer recurrence relations. In this post, we will learn another technique known as a recursion tree to solve the divide and conquer recurrences.
A recurrence tree helps to visualize every step of the recursion call. It shows the input size and time taken to process that input at a particular level. Using recursion tree, we can calculate the work done by the algorithm on each level. Summing the work done on each level gives the overall running time of the algorithm. Recursion trees can be useful to gain the intuition about the closed form of a recurrence relation.
We use following steps to solve the recurrence relation using recursion tree method.
- Create a recursion tree from the recurrence relation
- Calculate the work done in each node of the tree
- Calculate the work done in each level of the tree (this can be done by adding the work done in each node corresponding to that level).
- The sum over the work done in each level to get the solution.
Example 1: Consider a recurrence
$$T(n) = 2T(n/2) + n$$
There are 2 recursive calls in the recurrence. That means every node in the tree has two child nodes. The input size for each recursive call is $n/2$ which means each child of a node gets the half of the input i.e. if a parent node has input size $n$, each child will have input size $n/2$. The tree has the following form
In this example, each level has done the equal number of operations i.e. $n$ and there are $\log_2 n$ levels i.e. the height of the tree is $\log_2 n$. This is given in the figure below.
The total work is therefore,
$$n * \log_2 n = \Theta(n\log n$$
Example 2: Consider
$$T(n) = T(n/3) + T(2n/3) + n$$
It has two recursions with different input sizes. The left child gets input size $n/3$ and right child gets input size $2n/3$. As shown in the figure below, the tree is not a height balanced tree and therefore the height of the tree is the rightmost path (longest path) i.e. $\log_{3/2} n$. Each level of the tree does total $n$ work.
The total work is
$$n * \log_{3/2} n = \Theta(n\log n)$$