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?