Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is the Recursion Tree method?
2.1.
How is it useful?
2.2.
Why is it used?
3.
Steps of Recursion Tree method
3.1.
Step 1
3.2.
Step 2
3.3.
Step 3
4.
Solved Problems using the Recursion Tree Method
4.1.
Problem - 1
4.2.
Problem - 2
5.
FAQs
6.
Key Takeaways
Last Updated: Mar 27, 2024

Recursion Tree Method

Author Yukti Kumari
2 upvotes

Introduction

With an honest effort and after a lot of brainstorming, you have written a working code in your technical interview of your dream company. You take a sigh of relief.

But the interviewer asks you to explain the time and space complexity of your code.

So, to be confident in such situations, and flawlessly compute the complexity of your code, you must have a strong foundation of various techniques of analyzing time and space complexity and when to use them. 

 

In this article, we will see one of the most intuitive and helpful techniques to analyze time complexity which is the Recursion tree method. Usually, when we have recursive functions then after writing the recurrence relation, it seems ambiguous to compute the complexity from the equation. In such situations, the recursion tree comes to the rescue.

We will learn the steps to find time complexity using a recursion tree, and to make our understanding crystal clear; we will also solve some interesting problems in detail. 

Let’s get started.

 

Also see, Morris Traversal for Inorder.

Also see, Longest Common Substring

What is the Recursion Tree method?

As the name suggests, the Recursion tree consists of a root, and child nodes is a pictorial representation of a recurrence relation. Each node represents the cost of computing for a single subproblem of the original problem in a recursion tree.

How is it useful?

Unlike other algorithms, it is quite helpful for visualizing what happens in a recurrence relation.  

Why is it used?

A recursion tree is mainly used to generate a close guess to the actual complexity, which can be further verified using the substitution method. So, we should keep in mind that we can use recursion trees to develop an intuition of the underlying pattern, but they are not the actual proofs. 

Read More About, Data Structures and Algorithms and Data Structure.

Also read about - hash function in data structure.

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 - 2

 

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

  1. 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.
     
  2. 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. 
     
  3. What are the different types of time complexity?
    The various types of time complexities can be Constant Time, Linear Time, Logarithmic, Polynomial, Quadratic, Exponential.
     
  4. 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.
     
  5. 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!

Live masterclass