Why Intervals Are a Common Problem Pattern in DSA C - Performance Analysis

Time Complexity: Why Intervals Are a Common Problem Pattern

O(n log n)

Understanding Time Complexity

Intervals problems often involve checking or merging overlapping ranges. Understanding their time complexity helps us know how the solution scales as the number of intervals grows.

We want to find out how the number of steps changes when we have more intervals to process.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Sort intervals by start time
qsort(intervals, n, sizeof(Interval), compareStart);

// Merge overlapping intervals
int j = 0;
for (int i = 1; i < n; i++) {
    if (intervals[i].start <= intervals[j].end) {
        intervals[j].end = (intervals[j].end > intervals[i].end ? intervals[j].end : intervals[i].end);
    } else {
        j++;
        intervals[j] = intervals[i];
    }
}

This code sorts intervals and then merges any that overlap into one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the intervals and then one pass to merge them.
• How many times: Sorting takes multiple comparisons (depends on n log n), merging loops through all intervals once (n times).

How Execution Grows With Input

As the number of intervals grows, sorting takes more time, growing faster than just looping.

Input Size (n)	Approx. Operations
10	About 30 to 40 operations
100	About 700 to 800 operations
1000	About 10,000 to 12,000 operations

Pattern observation: The sorting step grows faster than the merging step, roughly proportional to n log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to process intervals grows a bit faster than just the number of intervals, mainly because of sorting.

Common Mistake

[X] Wrong: "Merging intervals is always O(n) because we just loop once."

[OK] Correct: Sorting the intervals first takes more time, so the total time includes that step, making it slower than just one loop.

Interview Connect

Understanding how sorting and merging combine helps you explain your solution clearly and shows you know how to handle common interval problems efficiently.

Self-Check

"What if the intervals were already sorted? How would the time complexity change?"