Question

time complexity of lcs is​

Answer 1

Answer:

Time complexity of the above naive recursive approach is O(2^n) in worst case and worst case happens when all characters of X and Y mismatch i.e., length of LCS is 0. In the above partial recursion tree, lcs(“AXY”, “AYZ”) is being solved twice.