int lcs_length(char * A, char * B)
{
if (*A == '\0' || *B == '\0')
return 0;
else if (*A == *B)
return 1 + lcs_length(A+1, B+1);
else
return max(lcs_length(A+1,B), lcs_length(A,B+1));
}
what is worst case time complexity of $\text{lcs_length}$ if size of $A$ is $m$ and size of $B$ is $n$?
- O($2^{m+n}$)
- O($2^{n}$)
- O($2^{mn}$)
- O($2^{max(m,n)}$)
- none of these