Recursion Tree Method

Recursion TreeThere are many times when recurrence happens in our software, for example, in merge sort, we break the algorithm into sub-problems, and then the sub-problems are divided into small sub-problems, making the sub-problems much simpler and easier to solve. The situation of merge sort requires a large amount of recurrence, and we must apply the recursion solution technique to calculate the cost and duration of this recurrence. The recursion tree is one of the recursion-solving methods. The asymptomatic notation is calculated using recursion tree algorithms. The recursion tree approach is a useful approach to make an informed estimate, but it will not be considered a satisfactory answer for computing the recurrence in the algorithm unless it is proven by another approach. This tree is a way of representing the algorithm’s iteration in the shape of a tree, with each node representing the tree’s iteration level. You’ll discover your solution in simpler words when we get to the last node of the tree.

Recursion Tree Solving Process


  1. The cost of the tree must be estimated and must be computed independently at each level of the tree.
  2. After determining the tree’s cost, we must determine the tree’s depth.
  3. Finally, we must determine the number of leaves on the tree.

Scenarios in Calculating Recursion Tree’s Cost

The following scenarios are used to calculate the recursion tree’s cost:

  1. Maximum Root Node Cost: In this situation, if the root node’s cost is higher than the cost of its child node, the cost of computing the root node becomes the cost of performing the algorithm.
  2. Maximum Leaf Node Cost: If the cost of the last level node is the highest in comparison to its parent node, the cost of the process is determined by the leaf node.
  3. Same Cost of Each Node: In this scenario, we must add the number of nodes to compute the process cost of operation.

Example 1

Consider the phenomenon of recurrence: T(n) = 2T(n/2) + n2. For this recurrence, the recursion tree looks like this:

Recurssion Tree Example

In this scenario, adding across each row of the tree to get the total work done at a particular level is simple:

Recurssion Tree Example Part2

Thus, this is a geometric series, the sum in the limit is O(n2). In this scenario, the tree’s depth is unimportant; the quantity of work at each level is dropping at such a rapid rate that the total is just a constant factor more than the root. Recursion trees are beneficial for developing intuition about a closed pattern of a recurrence, but they are not proofs. In reality, as with any approach that incorporates “…” forms of reasoning, it’s simple to get the erroneous result using a recursion tree. Making an informed estimate and then proving via induction that your hypothesis is truly a solution is a useful approach to constructing a closed form for a recurrence. Recurrence trees are a great way to make educated guesses.

Example 2

Consider the scenario: T(n) = T(n/3) + T(2n/3) + n. The recurrence tree, when expanded beyond the first few levels, is as follows:

Recursion Tree Example2

It’s worth noting that the tree isn’t balanced: the rightmost path is the longest, with a length of log3/2 n. As a result, we believe the closed-form of this recurrence is O. (n log n).

Add Comment