Recursive Tree Method for Solving Recurrences

For Complete YouTube Video: Click Here

In this class, we will try to understand the Recursive Tree Method for Solving Recurrences.

In our previous classes, we have seen how we can find the algorithm’s efficiency by using the substitution and master’s methods.

We have another method called the recursive tree method to find the efficiency of recursive algorithms.

Before finding the efficiency of an algorithm, we have to draw the recursive tree.

Consider the merge sort algorithm shown below to understand how to draw the recursive tree.

The function call made is MS(0, 7).

MS stands for Merge-Sort(0, 7).

To draw the recursive tree, we have to show all the function calls made by the MS(0, 7) to complete its execution, as shown below.

Similarly, we must show all the function calls for each function to complete its execution.

The illustration is shown below.

The above tree shows how the recursive tree is generated.

Now we will try to understand the order in which the function call is made while the algorithm is executed.

Traverse the recursive tree from top to bottom and from left to right, as shown below.

For better understanding click the YouTube link provided on the top of the page.