Recursion Tree Method (Iteration Method):
Recursion tree method is a graphical representation of an iteration method, which is the form of a tree where each level nodes are expended. It is useful when the divide and conquer algorithm is used. In recursion tree, each root and child represent the cost of a single problem.
Example 1– Solve the following recurrence relation using recursion tree method (iteration method).
T(n) = 2T(n/2) + n
Explanation:
In the above diagram, the recurrence relation divide into two sub problems. Understood? If not, then look at the recursive equation and diagram simultaneously. The diagram showing the actual meaning of the equation.
Again,
Now again,
T(n) = n + n + n + …. + (log2n times)
Why log2n times? Because the height of the tree is log2n.
T(n) = n*log2n
T(n) = O(nlog2n)
Example 2– Solve the following recurrence relation using recursion tree method (iteration method).
T(n) = 2T(n/2) + c; n>1
T(n) = c; n=1
Explanation:
Similarly as previous question-
T(n) = c + 2c + 4c + 8c + … + (log2n times)
T(n) = c[ 1 + 2 + 4 + 8 + … + (log2n times)]
Simply solve the G.P. inside the brackets.
T(n) = c[2log2n – 1] [2log2n = nlog22 = n]
T(n) = c[n – 1]
T(n) = O(n)
Example 3– Solve the following recurrence relation using recursion tree method (iteration method).
T(n) = T(n/3) + T(2n/3) + n
Explanation:
This question is somewhat different from above question. Why?
Because, in this question, the recurrence relation is divided into two different parts. In the above questions, the recurrence relation is divided into two equal parts.
Let’s see how to solve this one-
It is clear that the height of the tree is not balanced here. The height of the leftmost branch of the tree is log3n and the height of the rightmost branch of the tree is log3/2n.
So, the longest path is rightmost one, and its length is log3/2n.
Hence,
T(n) = n + n + n + …. + (log3/2n times)
Why log3/2n times? Because the height of the rightmost tree is log3/2n.
T(n) = n*log3/2n
T(n) = O(nlog3/2n)