What is the time complexity of the classical Dynamic Programming approach…
2024
What is the time complexity of the classical Dynamic Programming approach using nested loops for the LIS problem?
- A.
O(n)
- B.
O(n log n)
- C.
O(n²)
- D.
O(log n)
- E.
O(n³)
Attempted by 20 students.
Show answer & explanation
Correct answer: C
Concept
The Longest Increasing Subsequence (LIS) problem asks for the length of the longest subsequence whose elements are in strictly increasing order. The classical dynamic-programming formulation defines dp[i] as the length of the longest increasing subsequence that ends exactly at index i. The governing recurrence is: dp[i] = 1 + max(dp[j]) over every earlier index j < i for which arr[j] < arr[i], and dp[i] = 1 when no such j exists.
Application to this problem
Evaluating that recurrence with two nested loops proceeds as follows:
Outer loop: iterate i from 0 to n-1, initialising each dp[i] = 1.
Inner loop: for each i, scan every earlier index j from 0 to i-1 and, whenever arr[j] < arr[i], update dp[i] = max(dp[i], dp[j] + 1).
Answer: the LIS length is the maximum value over all dp[i].
The inner loop performs up to i comparisons for each i, so the total work is 1 + 2 + ... + (n-1) = n(n-1)/2 comparisons. This sum is of the order n2, because the two nested loops each run proportional to n.
Cross-check
A faster n log n method exists (patience-sorting with binary search), but that is a different algorithm, not the nested-loop DP being asked about. A single pass would be n, which cannot examine all earlier elements; a triple nesting would be n3, which the recurrence never requires. The nested-loop DP sits exactly between these.