Longest Common Subsequence

Question

For finding longest common subsequence(LCS), standard sources mention that the recursive procedure consisting of the recursive tree occupies O(m+n) space( WITHOUT applying Dynamic Programming). I am unable to understand why is space occupied O(m+n)?

Consider the tree of LCS(3,3). Won't the tree height( which is equal to the height of recursion stack and hence space occupied) be equivalent to log of (m+n), as in, the sequence can be evaluated as 2^0+2^1^2^2+...................2^k(worst case) where k will be the number of levels. So, the value of2^ k = O(m+n) and hence, space should be k=log(m+n).

What's wrong with my logic?

Comments

take for example

L1=aaa

L2=bbb

now,the function call would be like

                     f(3,3)

         |                                             |

        f(2,3)                                          f(3,2)

    |                     |                            |                        |

  f (2,2)            f(1,3)                  f(3,1)               f(2,2)

|          |         |           |               |           |              |           |

f(1,2)   f(2,1) f(1,2)  f(0,3)     f(3,0)   f(2,1)     f(2,1)      f(1,2)

|       |

f(1,1) f(0,2)

|

f(1,0)

so,see here the height of tree,it is 6 function calls long,which is worst case when both strings are entirely different.

Answer 1

You are just doing a small mistake...

first thing: as you can see when you implement the algorithm of LCS you will get the tree of the level (m+n)

second thing: if you are getting level= (m+n) it means the height of stack will definitely go up to (m+n).

now you can see the height of the stack is (m+n) still you are saying that stack space should be log(m+n) 

in recursion tree number of nodes represent function calls and the number of levels represents the stack space...

so here you are mistaken in the concept of function calls and levels of recursion tree. Always remember the number of levels represents stack space and number of nodes represent function calls. In the above tree if you count total nodes and take log of it you will definitely get 6 =(m+n)