Longest Increasing Subsequence in DSA Typescript - Time & Space Complexity

Time Complexity: Longest Increasing Subsequence

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find the longest increasing subsequence changes as the input list grows.

How does the number of steps increase when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array(n).fill(1);
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }
  return Math.max(...dp);
}
    

This code finds the length of the longest increasing subsequence by checking all pairs of elements.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops comparing pairs of elements.
• How many times: Outer loop runs n times; inner loop runs up to i times, so roughly n x n = n² times.

How Execution Grows With Input

As the list size grows, the number of comparisons grows much faster because each new element is compared with all before it.

Input Size (n)	Approx. Operations
10	About 100 comparisons
100	About 10,000 comparisons
1000	About 1,000,000 comparisons

Pattern observation: Operations grow roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if the input list doubles in size, the work needed grows about four times.

Common Mistake

[X] Wrong: "The algorithm only looks at each element once, so it must be O(n)."

[OK] Correct: Each element is compared with many others inside nested loops, so the total steps add up much more than just once per element.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and shows you can analyze nested loops clearly, a key skill in interviews.

Self-Check

"What if we used a binary search approach inside the loop to improve the search? How would the time complexity change?"