educative.io

Brute force solution complexity

Courses
,
#1

Shouldn’t the time complexity for the brute force solution be 3^n, because we are making up to 3 recursive calls in each call?

#2

Hi @Hasan_Zaidi,

This is a little tricky. If you see closely, we either make one recursive call or two recursive calls. So, in total, each function will not make more than two recursive calls, therefore the time complexity is O(2^n).

Here are the relevant lines:

if(st.charAt(startIndex) == st.charAt(endIndex))
  return 2 + findLPSLengthRecursive(st, startIndex+1, endIndex-1);

// case 2: skip one element either from the beginning or the end
int c1 =  findLPSLengthRecursive(st, startIndex+1, endIndex);
int c2 =  findLPSLengthRecursive(st, startIndex, endIndex-1);
return Math.max(c1, c2);

See the two return statements.

Hope this answers your question.

1 Like
#3

OK. Although shouldn’t the value returned by the single recursive statement be compared to c1 and c2, in case c1 or c2 is larger?

#4

c1 and c2 can never be bigger than the value returned by the single recursive call. The best the two recursive call can have is with a string like “bbcacb”, where, after skipping the first char, the remaining string is LPS. Let’s see what singe recursive call and c1 will be in this case.

Since the first and the last char are same, so we go into the single recursive call with “bcac”. For the remaining string after skipping the first char “b”, we get “cac”. So overall the LPS will be: bcacb

No suppose, we try to find c1 in this case. The best we can have is “bcacb” after skipping the first char.

In both cases, the length (and the actual) LPS are the same.

Hope this answers your question.

#5

OK, that makes sense. Although then shouldn’t Longest Palindromic Substring be O(3^n): https://www.educative.io/collection/page/5668639101419520/5633779737559040/5661601461960704

as that makes 3 calls and does a Max on all 3?

#6

That is true. We will fix it.

#7

Thanks… It did help :slight_smile: