educative.io

Educative

Complexity of BruteForce Recursive Solution

Sir,

I think the BruteForce solution can be slightly modified to look like this
public static int lcsRecursive(String s1, String s2, int i1, int i2, int count) {
if (i1 == s1.length() || i2 == s2.length()) {
// we reached the end
return count;
}
if (s1.charAt(i1) == s2.charAt(i2)) {
//so increment the count and try to recursively match for remaining lenght (the next set of chars)
return lcsRecursive(s1,s2,i1+1,i2+1,count+1);
}

    //if strings do not match create two new recursive calls by skipping one char separately
    int c1 = lcsRecursive(s1,s2,i1+1, i2, 0);
    int c2 = lcsRecursive(s1,s2,i1, i2+1, 0);

    return Math.max(count, Math.max(c1,c2));
}

And then the complexity would be O(2^(m+n)) and not 3^(m+n)
The above code can be expressed by recurrence relation
T(n) = 1 + T(n-1) + T(n-1)
And so
T(n) = O(2^(m+n))
please let me know …