time complexity of recursive function

I am solving the LCS problem with naive recursion.

I dont understand why the worst case complexity is 2^n

/* A Naive recursive implementation of LCS problem 
   so what is the recurrence relation for this program */

// Returns length of LCS for X[0..m-1], Y[0..n-1]

int lcs( char *X, char *Y, int m, int n )
{

    if (m == 0 || n == 0) // if length of any sequence becomes 0 return 0
        return 0;

    if (X[m-1] == Y[n-1]) // if last elements are same then it must be
                          // in longest sequence so it is appended to lcs
        return 1 + lcs(X, Y, m-1, n-1);

    // what is the recurrence relation for this function

    else
        return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}

can anyone explain the recurrence relation.

Solution

Assuming that n = max(m, n), you can consider each function call as a node in a tree. In the worst case, X[m-1] != Y[n-1] for any of the instances in the string. In that case, for each node in the tree, we make two function calls, or branches down to two child nodes. Thus, we are building a fully populated binary tree that is of depth n. A binary tree of this depth will have 2^n - 1 nodes (https://math.stackexchange.com/questions/141783/the-maximum-number-of-nodes-in-a-binary-tree-of-depth-k-is-2k-1-k-geq1) and since we defined a node as a function call, the running time is on the order of 2^n - 1 => O(2^n).