There 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
- The cost of the tree must be estimated and must be computed independently at each level of the tree.
- After determining the tree’s cost, we must determine the tree’s depth.
- 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:
- 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.
- 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.
- 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:
In this scenario, adding across each row of the tree to get the total work done at a particular level is simple:
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:
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).