Steps of Recursion Tree method
There are mainly three steps in the recursion tree method. In this section, we will learn each of them one by one.
Step 1
- Construct a recursion tree from the recurrence relation at hand.
Step 2
- Find the total number of levels in the recursion tree.
- Compute the cost of each level in the tree.
- Calculate the total number of nodes in the last level or the leaf nodes.
- Compute the cost of the last level.
Step 3
- Sum up the cost of all the levels and decompose the expression obtained in the standard asymptotic notation.
Solved Problems using the Recursion Tree Method
You already know the steps you should follow in the recursion tree method from the previous section. So, to realize the theoretical concepts in practice, in this section, we will solve some interesting recurrence relations by following the steps of the recursion tree method.
Problem - 1
Consider the recurrence relation: T(n) = 2T(n/2) + n
We have to first understand what does the given relation implies.
So, from the above relation, you can deduce that -
- A size n is divided into two subproblems, each of size n/2.
- It takes O(n) time extra to compute T(n) finally.
We can draw the recursion tree as -
The total number of levels in the tree is:
- Base case occurs when the problem size reaches 1.
So, let's see at which level the size of the subproblem becomes 1
The size of the subproblems at different levels are:
- Level 0 - n = n/20
- Level 1 - n/2 = n/21
- Level 2 - n/4 = n/22
- Level i - n/2i
Let the level at which the size of the subproblem becomes 1 is y.
Then,
=> n/2y = 1
=> n = 2y
=> Taking log base 2 both sides
=> log2(n) = y
So, total number of levels is y+1 = log2(n) + 1.
Number of nodes in each level are:
- Level 0 - 1 = 20
- Level 1 - 2 = 21
- Level 2 - 4 = 22
- Level i - 2i
So, number of nodes at the last level is 2^(level_number) = 2^(log2(n)) = n
Hence the cost of the last level is = Number of nodes x Cost of each node, which is nxT(1) = O(n).
The cost of all the levels are -
- Level 0 - n
- Level 1 - n/2 + n/2 = n (As there are two subproblems each of size n/2)
- Level 2 - n/4 + n/4 + n/4 + n/4 = n
- and so on…
Summing up we get the total cost as -
=> (n+ n+ n+...n) + Cost of the last level
=> nxlog2(n) + O(n)
=> O(nlog2(n))
Must Read Recursion in Data Structure and Application of Graph in Data Structure
Problem - 2
Consider the recurrence relation: T(n) = T(n/3) + T(2n/3) + n
The recursion tree for the given relation is:
Total number of levels
Here a problem of size n is divided into two subproblems of different sizes i.e. n/3 and 2n/3 or n/(3/2), which means that all the leaf nodes will not lie at the same level. So, we need to find the level of the deepest leaf node in the tree.
Since among the branching factors of 3 and 3/2, 3/2 is smaller than 3, so the deepest leaf node will occur in the path -
T(n) → T(2n/3) → T(4n/9) → …….
Let the last level be y and we know that the base case is n=1.
So, (â…”)yn = 1
=> n = (3/2)y
=> Taking log base 3/2 on both sides
=> log3/2(n) = y
Hence, total number of levels = y+1 = log3/2(n) + 1.
Number of nodes in each level
- Level 0 - 1
- Level 1 - 2
- Level 2 - 4
- Level i - 2i
So, number of nodes in the last level y=log3/2(n) is 2^y = 2^(log3/2(n))
Cost of all the levels
- Level 0 - n
- Level 1 - n/3 + 2n/3 = n
- Level 2 - n/9 + 2n/9 + 2n/9 + 4n/9 = n
- Level i - n
Summing up we get -
=> (n+ n+ n+...n) + Cost of the last level
=> nlog3/2(n) + O(log3/2(n))
=> O(nlog3/2(n))
Read More - Time Complexity of Sorting Algorithms and Rabin Karp Algorithm
FAQs
-
Why is the recursion tree method used?
A Recursion Tree is used to generate a close guess, which can be verified by the Substitution Method.
-
What does time complexity depend on?
The number of machine instructions that a program executes during its execution determines its time complexity in computer science.
-
What are the different types of time complexity?
The various types of time complexities can be Constant Time, Linear Time, Logarithmic, Polynomial, Quadratic, Exponential.
-
What is the difference between the recursion tree method and the substitution method?
A Recursion Tree is used to generate a close guess, which can be verified by the Substitution Method.
-
How do you figure out the time and space complexity of recursive function?
The space complexity of a recursive algorithm is proportional to the maximum depth of the recursion tree generated.
Key Takeaways
In this article, we learnt one of the most intuitive and helpful methods of computing the time complexity of algorithms i.e. the recursion tree method.
We saw the steps to follow in the recursion tree method along with solved examples to get a practical understanding of the concept.
There are many more methods of analyzing time and space complexities.
You must check out -
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!