# 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**b**operations.^{d} - ~ O(b
^{d})

## 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.

- As we call the function

### Time complexity:

**O(3**, at the least^{min(m,n)})**O(3**, at worst case and it occurs when m=n^{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.