#self doubt #Lcs

Question

How many distinct function calls are there in LCS(m,n)=. How to calculate it?

Answer 1

In the LCS (m,n) without using the dynamic programming, the total no. of function call will be O(2^m+n) (in the worst case) total call because of the left side of the binary tree has m level of the tree and right level has n level of the binary tree.

and after using the dynamic programming the (only distinct function will be call ) than O(m*n) function call.

u can take the example like LCS(5,4) using the recurrence relation of LCS.

LCS(m,n)= {  o if y[m] == 0 II x[n]== 0

                  { 1 +LCS(m-1,n-1) if y[m] = =x[n]

                  {  Max (LCS(m-1,n) ,LCS(m,n-1)) if  if y[m]  !=x[n]

Comments

@Things To Know (Thin ,you are saying  left subtree have m level and right subtree has n level -no this is wrong ,either m will decrease or n will decrease that's why total height of tree is m+n in both side ,so tree become almost complete binary tree so tota no. Of functions calls =$O(2^{m+n})$