Per the standard DP solution for LCS of two strings of length m and n, the running time is
AO(m + n) using two pointers
BO(m log n) with a sorted table
CO(2^(m+n)) since both characters must be tried
DO(mn) by filling an m × n DP table
Answer & Solution
Correct answer: D. O(mn) by filling an m × n DP table
Each cell of the m × n DP table is computed in O(1) by checking three neighbours and applying the recurrence. Total: O(mn). The two-pointer O(m+n) approach gives merge-style scanning but not LCS. The 2^(m+n) figure is the naive recursion before memoisation; DP collapses it to polynomial.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for