edited by
397 views
0 votes
0 votes
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$?

  1. O($2^{m+n}$)
  2. O($2^{n}$)
  3. O($2^{mn}$)
  4. O($2^{max(m,n)}$)
  5. none of these
edited by

1 Answer

Best answer
1 votes
1 votes

time complexity= total no of function coll= O($^{2^m^+^n}$

                                    

selected by

Related questions

1 votes
1 votes
0 answers
2
kartikeya2812 asked Jun 16, 2018
387 views
What will be the time complexity of the following algorithm ?A(n){if(n<=1) return 1;for(i=1;i<n;i++){ for(j=0;j<3;j++){ A(n-1) } }}
7 votes
7 votes
3 answers
3
bts asked May 29, 2018
1,827 views
Why is recursive equation of following code $T(n)=T(n/2)+O(1)$, not $T(n)=8*T(n/2)+O(1)$? int x=0; int A(n) { if(n==1) return 1; else { X+=8A(n/2)+n^3; } return X; }
5 votes
5 votes
0 answers
4
Mk Utkarsh asked Jan 9, 2018
407 views
T(n) $\leq$ T($\frac{n}{5}$) + T($\frac{7n}{10}$) + 15nT(n) $\leq$ 5 when n $<$ 6