The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
72 views
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
asked in Algorithms by Active (2.7k points)
edited by | 72 views

1 Answer

+1 vote
Best answer

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

                                    

answered by Boss (23.3k points)
selected by
0
beautiful explanation! thanks!


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,753 questions
46,768 answers
140,672 comments
58,545 users