0
$\begingroup$

I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches:

  1. Recursive Algoritm
  2. Dynamic Programming

Dynamic programming should be the better option in this case because of the time complexity but the time complexity of both algorithms is $O(n^2)$. My question is if the time complexity is the same for both algorithms, why is the dynamic programming approach considered better than recursive solution? I'm following the algoritms in this post. It says that the time complexity of dynamic programming algorithm is much better than the worst case time complexity of naive recursive implementation. What could be the worst case?

$\endgroup$
2
$\begingroup$

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 <stdio.h>
#include <string.h>

int max (int x, int y) {return (x > 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] && 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 <= 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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.