Longest Increasing Subsequence in DSA C - Time & Space Complexity

Time Complexity: Longest Increasing Subsequence

O(n²)

Understanding Time Complexity

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

How does the number of steps grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int lengthOfLIS(int* nums, int numsSize) {
    int* dp = malloc(numsSize * sizeof(int));
    int maxLen = 1;
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > maxLen) maxLen = dp[i];
    }
    free(dp);
    return maxLen;
}
    

This code finds the length of the longest increasing subsequence in an array by checking all previous elements for each position.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops comparing each element with all previous elements.
• How many times: Outer loop runs n times; inner loop runs up to i times, so roughly n times on average.

How Execution Grows With Input

For each new element, the code checks all earlier elements to update the subsequence length.

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

Pattern observation: The number of operations grows roughly by the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if the input size doubles, the time to run roughly quadruples.

Common Mistake

[X] Wrong: "The algorithm runs in linear time because it just loops through the array once."

[OK] Correct: There is a nested loop inside the main loop, so the total steps multiply, making it slower than just one loop.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and shows you can analyze nested loops clearly.

Self-Check

"What if we used a binary search method inside the loop to find the position instead of checking all previous elements? How would the time complexity change?"