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

Time Complexity: Insert Interval into Sorted List

O(n)

Understanding Time Complexity

We want to understand how the time needed to insert a new interval into a sorted list of intervals changes as the list grows.

Specifically, how does the number of steps grow when we add one interval to many sorted intervals?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def insert_interval(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

This code inserts a new interval into a sorted list of intervals, merging overlapping intervals.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three while loops that each traverse parts of the intervals list.
• How many times: Each loop moves forward through the list without going back, together covering all intervals once.

How Execution Grows With Input

As the number of intervals grows, the code checks each interval at most once to find where to insert and merge.

Input Size (n)	Approx. Operations
10	About 10 checks and merges
100	About 100 checks and merges
1000	About 1000 checks and merges

Pattern observation: The number of operations 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, we can insert the interval in constant time without checking all intervals."

[OK] Correct: Even though the list is sorted, we must check intervals to find overlaps and merge them, which requires looking at many intervals in the worst case.

Interview Connect

Understanding this linear time complexity helps you explain how to efficiently handle interval merging, a common problem in coding interviews and real-world scheduling tasks.

Self-Check

"What if the intervals list was not sorted? How would the time complexity change?"