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^d operations.
~ 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.

Time complexity:

O(3 ^min(m,n)) , at the least
O(3ⁿ) , 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.

VitaminAlgo