Complexity of Longest Palindromic Subsequence Algorithm
The dynamic programming approach is indeed O(n^2).
However, the recursive solution is exponential in n: any time two characters don't match, a subproblem of size k is converted into 2 subproblems of size k-1 each.
It's easy to see that, with all letters different, this produces a complexity of O(2^n).

Here is the example from the page you mention, modified to count and output the number of calls.
A local copy to prevent link rot:

#include &lt;stdio.h&gt;
#include &lt;string.h&gt;

int max (int x, int y) {return (x &gt; y) ? x : y;}

int count;

int lps (char * seq, int i, int j)
{
   count += 1;
   if (i == j)
      return 1;
   if (seq[i] == seq[j] &amp;&amp; i + 1 == j)
      return 2;
   if (seq[i] == seq[j])
      return lps (seq, i + 1, j - 1) + 2;
   return max (lps (seq, i, j - 1), lps(seq, i + 1, j));
}

int main ()
{
    char seq [] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int n = 1; n &lt;= 26; n++)
    {
       count = 0;
       printf ("n = %d: answer = %d", n, lps (seq, 0, n - 1));
       printf (", count = %d\n", count);
    }
    return 0;
}


The output is:

n = 1: answer = 1, count = 1
n = 2: answer = 1, count = 3
n = 3: answer = 1, count = 7
n = 4: answer = 1, count = 15
n = 5: answer = 1, count = 31
...
n = 24: answer = 1, count = 16777215
n = 25: answer = 1, count = 33554431
n = 26: answer = 1, count = 67108863