I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches:
- Recursive Algoritm
- 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?