CODEWITHSUNDEEP
c++algorithmrecursionbig-o
nogeek001
nogeek001

Reputation: 723

Big O for the following recursive solution

I have written the following code for finding the minimum deletion distance between two strings

enter code here
#include <iostream>
#include <string>

using namespace std;
int  DeletionDistance(const string& str1, const string& str2, int len1, int  
len2){
int index1=0;
int index2=0;
int count=0;
int str1len=str1.length();
int str2len=str2.length();
//calculate the base case if a string is empty, the deletion distance is the 
length of the other string
//since we need to delete all the other chars from the non empty string in 
order to match the two strings
if(str1len<=0)
  return str2len;
else if(str2len<=0)
  return str1len;
else{
//the strings are non empty. Recursively calculate the min del distance 
  if(str1[index1]==str2[index2]){
     //the chars match , hence the deletion distance would depend on the 
       remaining chars in both strings
      return DeletionDistance(str1.substr(index1+1,len1), 
                              str2.substr(index2+1,len2), len1, len2);  
  }
  else
    //the chars dont match 
    return (1+min(DeletionDistance(str1.substr(index1+1,len1), 
                                   str2.substr(index2,len2), len1, len2),
                  DeletionDistance(str1.substr(index1,len1), 
                                   str2.substr(index2+1,len2), len1, 
                                   len2)));
    }
}

 int deletionDistance( const string& str1, const string& str2 ) 
 {
  int len1 = str1.length();
  int len2 = str2.length();
  return DeletionDistance(str1, str2, len1, len2);

 }

In this code , where we recursively calculate the minimum deletion distance between two strings how does one calculate the Time and Space complexity? I was told that the time and space complexity for this solution is O(ab) where, a = len of string 1 b = len of string 2 I would really appreciate some explanation or pointers on how to start calculating Big O for recursive solutions like this. I was able to calculate bigO for simpler recursive solutions like Fibonacci series , factorial etc , but this beats me.

Upvotes: 0

Views: 102

Answers (1)

Said A. Sryheni
Said A. Sryheni

Reputation: 757

The complexity of your code is O(2 ^ (|A| + |B|) ), where |A| and |B| are the sizes of the first and second strings respectively.

The reason for this is that in the worst case your recursion will return when it reaches the last character in both strings. Inside your code, each time you are advancing one step forward either in the first or in the second string. So in general your recursion has a depth of (|A| + |B|), and your code contains 2 recursive calls.

As mentioned in the comments you can achieve a complexity of O(|A| * |B|) using dynamic programming. Here is a nice tutorial that will walk you through it. Your problem is close to the Longest Common Subsequence problem (LCS).

Upvotes: 1

Related Questions