There are lot of time when the recurrence occurs in our program in our sorting algorithm for example in merge sort we divide the algorithm into sub problem and then again the sub problem is divided into mini sub problem, the sub problems are much simpler and easy to solve. The case of merge sort involves a great amount of recurrence and to figure the cost and time of this recurrence we have to use recursion solving method.
One of the recursion solving method is Recursion tree.
Recursion tree methods are used to calculate the asymptomatic notation. With the help of this notation we can calculate the cost and time complexity of our algorithm which will be used in running process.
Recursion means the function which can call itself or repeat itself any number of time, and tree is a type of data structure where our data is represented with parent nodes and their branching out child nodes.
The recursion tree usability increases when the divide and conquer problems are used.
Also remember, recursion tree method is a good way to make an educated guess but until it is verified by some other method it will not be considered as a good solution of calculating the recurrence in the algorithm. The best method to verify the recurrence is the substitution method, you can make a quick guess of the problem with the help of the recursion tree and you can verify the guess into an applicable solution with the help of the substitution method.
This tree is a method to represent the iteration of the algorithm in form of the tree and each node represent the iteration level of the tree.
When we reach the last node of the tree you will find your solution in the simpler terms.
The cost of the algorithm will be determined by adding the value at every level.
When solving any recursion tree we have to follow some process.
- We have to calculate the cost of the tree, the cost of the tree is calculated separately at every level of the tree.
- After calculating the cost of the tree we have to calculate the depth of the tree.
- At the end we have to calculate the number of the leaves of the tree.
In calculating the cost of the recursion tree we have many cases
- Cost of the root node is maximum, in this case if the cost of the root node is comparatively larger than its child node than the cost that incurs in calculating the root node becomes the cost of the running of algorithm.
- Cost of the leaf node is maximum, in this case if the cost of last level nodes are maximum comparatively to its parent node than the leave node determines the cost of the process.
- Cost of each node is same, in this case we have to combine the number of nodes to determine the cost of running of the process.
Now we come to recurrence relation, recurrence relation is a concept of discrete mathematics which is very useful in algorithms.
The recurrence relation in algorithm gives the number of the sub problem that the main problem can be divided and also the time of the problem which is required to calculate the problem at each level.
The recursive node helps to determine the number of the sub-problem that is present in the recursive method , this is the extra information that the recursive tree gives us that how many sub problems are within the same problem.
The process of creating a recursion tree
To make the recursion tree we have to identify which term has to be the root node and which node will be the child node.
You have to keep on expanding the node so that the till the value of n becomes when one and then the child node will become the leave node .
The cost of the work done by every level will be different and summing them will give us the total work done at every level.