The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
80 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.8k points)
edited by | 80 views

1 Answer

+1 vote
Best answer

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

                                    

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

Related questions



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

44,240 questions
49,722 answers
163,928 comments
65,839 users