alleryStart learning →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.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.