Big O for the following recursive solution

Question

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.

Not an answer to your question, but the len1 and len2 parameters seem completely pointless. — Michael Burr
– Michael Burr, Commented Feb 11, 2018 at 2:50
Your solution here is I believe O(2^min(a,b)), but it would be O(ab) if you used some kind of memoization (which you are not here). It would be nice to better to hear from an algorithm master than from me, but I believe this is the case. — Seoul
– Seoul, Commented Feb 11, 2018 at 3:01
@MichaelBurr I had added those variables solely for code readability. — nogeek001
– nogeek001, Commented Feb 11, 2018 at 3:59

Said A. Sryheni · Accepted Answer · 2018-02-11 08:06:41Z

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

Collectives™ on Stack Overflow

Big O for the following recursive solution

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related