Complexité du plus long algorithme de subséquence palindromique

Question

J'essaie de trouver la plus longue subséquence palindromique pour n'importe quelle chaîne et j'ai essayé deux approches:

1. Algoritm récursif
2. Programmation dynamique

La programmation dynamique devrait être la meilleure option dans ce cas en raison de la complexité du temps, mais la complexité temporelle des deux algorithmes est $ o (n ^ 2) $. Ma question est de savoir si la complexité du temps est la même pour les deux algorithmes, pourquoi l'approche de programmation dynamique est-elle considérée comme meilleure que la solution récursive? Je suis les algorits dans ce post. Il indique que la complexité temporelle de l'algorithme de programmation dynamique est bien meilleure que la complexité de temps du pire des cas de la mise en œuvre récursive naïve. Quel pourrait être le pire des cas?