educative.io

How to calculate the basic solution time complexity and Top-down array question?

Courses
,
#1

  1. How do we calculate the the basic solution time complexity? In solution, it’s O(3^(m + n)). how to get this result?

  2. Why do we need three-dimensional array in Top-down solution? i1 and i2 are changing values and count is the result we want. We can just use two-dimensional array for i1 and i2.

  3. Why can’t we pass count instead of 0 as the argument in c1 and c2 in basic solution just like we pass the sum in Maximum Sum Increasing Subsequence basic solution?

    This problem basic solution:
    int c1 = findLCSLengthRecursive(s1, s2, i1, i2+1, 0);
    int c2 = findLCSLengthRecursive(s1, s2, i1+1, i2, 0);
    Maximum Sum Increasing Subsequence basic solution:
    int s2 = findMSISRecursive(nums, currentIndex+1, previousIndex, sum);

  4. Can we not use count as parameter in basic solution just like the solution of Longest Common Subsequence? If so, how to change the code?

Do you guys have any ideas? Thanks!

#2

Hi @Franklin,

Here are the answers to your questions:

  1. There are three recursive calls in each function call and we are iterating both the strings; that is why we have a time complexity of O(3^(m + n)). Compare it with the case when we are iterating only one string and make two recursive calls; in that case the time complexity will be O(2^n).

  2. ‘Count’ is also a changing variable, see this:

    if(s1.charAt(i1) == s2.charAt(i2))
   count = findLCSLengthRecursive(s1, s2, i1+1, i2+1, count+1);

So we do need a three-dimensional array.

3 & 4. Both these questions are because you are confusing ‘substring’ and ‘subsequence’. When we are matching a substring we have to find contiguous characters; that is why whenever we don’t have a matching character we restart the count to ‘0’ as now we will be finding a new string.

In case of a subsequence, we can always skip a character as there can be extra characters in a subsequence of a sequence.

Hope these answers help.

1 Like