# VitaminAlgo # Method to determine complexity from the Recursion Tree

Let us take an example recursion tree, C being the function called recursively, T(1) as base case. Code interpretation can look like this,

``````function C(param) {
if(param == some condition) //Base Case // Leaf
return 1 // T(1)
//do something
C(paramNew1) //next computation // branch 1 to the  recursion tree
C(paramNew2) //next computation // branch 2 to the recursion tree
....
}
``````
• Notice two things:
• tree depth is the total number of return statements executed until we reach base case , along the most distant node from the root of the tree.
• In above diagram it is n-1.
• tree breadth is total number recursive function calls that are made at a given time.
• In above diagram it is 2. A function , at a given time, it is getting split into two more functions.

## Time Complexity Analysis

• Draw the recursion tree
• For arbitrary `n` , find out the depth `d` of the tree as `f(n)`
• Find out average branching factor `b` i.e. how many children are present per node on average
• If we want to visit every node in a tree of depth `d` with branching factor `b` , we take at least bd operations.
• ~ O(bd)

## Space Complexity Analysis

• Memory complexity is determined by the number of recursion calls ( which are stored on program stack )
• ~ O(recursion depth)

# Example - Edit Distance

Let us take example from the previous post

## Code

``````    public int minDistance(String word1, String word2) {
return ED(word1,word2,0,0);
}

private int ED(String s1, String s2, int i, int j){
if(i==s1.length())
return s2.length()-j; // remaining size difference

if(j==s2.length())
return s1.length()-i; // remaining size difference

if(s1.charAt(i) == s2.charAt(j))
return ED(s1,s2,i+1,j+1); //cost = 0
else
return Math.min(Math.min(
ED(s1,s2,i,j+1), //insertion
ED(s1,s2,i+1,j)), //deletion
ED(s1,s2,i+1,j+1)) //substitution
+ 1; //cost = 1 for Levenshtein
}
``````

## Complexity Analysis

Using Method to determine complexity from the Recursion Tree , let's say,

• `s1` is the first string and `s2` is the second string
• s1 is of `m` length and s2 is of `n` length
• So, Depth `d` of the tree will be `min(m,n)`.
• As, we terminate early when we have finished iterate over the smaller string.
• And, Branching factor `b` will be `3`.
• As we call the function `ED` recursively, for insertion, deletion and substitution.

### Time complexity:

• O(3 min(m,n)) , at the least
• O(3n) , at worst case and it occurs when m=n

### Space complexity:

• O(n) at the worst case

# Questions

The time complexity is exponential in nature. In what test case will it be inefficient for Edit Distance? Why?

hint!

``````"dinitrophenylhydrazine"
"acetylphenylhydrazine"
``````

Try to draw the recursion tree for this example and find out when does this become inefficient.

Stay tune for the solution in the next blog and understand why it is inefficient. Also, we will explore next approaches to make the Edit Distance algorithm efficient.

Below is a Map of things we have written so far. Also, we would like to hang with people who are doing these algorithms. Join us at Discord or follow us over Twitter/Instagram. 