educative.io

Time complexity for basic solution

Courses
,
#1

The time complexity for the basic solution is given as 2^(m + n). But shouldn’t it be 2^n or 2^m depending on whether n or m is smaller because the basic solution stops when you reach the end of either of the Strings, not both Strings?

#2

Hi Hassan,

If you see closely we do make recursive calls for every index of the strings:

int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1);
int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2);

So in the worst case we will be making O(2^(m+n)) calls. You can try this by drawing the recursion tree for two strings and then counting the number of recursive calls in the worst case.

#3

How come the substring version is base 3 complexity whereas 2 here. Same number of calls no?

#4

If the characters match s1.charAt(i1) == s2.charAt(i2). We return the value for the method instead of running it against the remainder of the two calls. Hence if the characters do no match we arrive at our worst case of running it against the two remaining recursive calls.