Insert Interval into Sorted List in DSA C - Time & Space Complexity

Time Complexity: Insert Interval into Sorted List

O(n)

Understanding Time Complexity

We want to know how the time to insert a new interval into a sorted list changes as the list grows.

Specifically, how many steps does it take to find the right place and merge intervals if needed?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void insertInterval(int intervals[][2], int* size, int newInterval[2]) {
    int i = 0, pos = 0;
    while (i < *size && intervals[i][1] < newInterval[0]) i++;
    pos = i;
    while (i < *size && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = (intervals[i][0] < newInterval[0]) ? intervals[i][0] : newInterval[0];
        newInterval[1] = (intervals[i][1] > newInterval[1]) ? intervals[i][1] : newInterval[1];
        i++;
    }
    // Shift intervals and insert merged newInterval at pos
    // ... (shifting code omitted for brevity)
}
    

This code finds where to insert a new interval in a sorted list and merges overlapping intervals.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two while loops scanning parts of the intervals array.
• How many times: Each loop runs at most n times combined, where n is the number of intervals.

How Execution Grows With Input

As the number of intervals grows, the loops scan through the list to find overlaps and insertion point.

Input Size (n)	Approx. Operations
10	Up to 10 steps scanning intervals
100	Up to 100 steps scanning intervals
1000	Up to 1000 steps scanning intervals

Pattern observation: The number of steps grows roughly in direct proportion to the number of intervals.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert grows linearly with the number of intervals in the list.

Common Mistake

[X] Wrong: "Since the list is sorted, insertion can be done in constant time."

[OK] Correct: Even though the list is sorted, we must scan to find the correct position and merge overlaps, which takes time proportional to the list size.

Interview Connect

Understanding how to efficiently insert and merge intervals is a common skill that shows your ability to work with sorted data and handle edge cases.

Self-Check

"What if the intervals were stored in a balanced tree instead of an array? How would the time complexity change?"