Date range overlap detection in SQL - Time & Space Complexity

Time Complexity: Date range overlap detection

O(n²)

Understanding Time Complexity

We want to understand how the time needed to find overlapping date ranges changes as the number of date ranges grows.

How does checking each pair for overlap scale when we have more date ranges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.id
FROM bookings a
JOIN bookings b ON a.id < b.id
  AND a.start_date <= b.end_date
  AND a.end_date >= b.start_date;
    

This query finds all pairs of bookings where the date ranges overlap.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing each booking with every other booking to check for overlap.
• How many times: For n bookings, roughly n x (n - 1) / 2 comparisons happen.

How Execution Grows With Input

As the number of bookings grows, the number of comparisons grows much faster.

Input Size (n)	Approx. Operations
10	About 45 comparisons
100	About 4,950 comparisons
1000	About 499,500 comparisons

Pattern observation: Doubling the number of bookings roughly quadruples the comparisons.

Final Time Complexity

Time Complexity: O(n²)

This means the time to find overlaps grows quickly as the number of bookings increases, because each booking is checked against many others.

Common Mistake

[X] Wrong: "Checking overlaps only takes time proportional to the number of bookings (O(n))."

[OK] Correct: Because each booking must be compared with many others, the total checks grow much faster than just the number of bookings.

Interview Connect

Understanding how pairwise comparisons grow helps you explain performance in real systems that handle scheduling or reservations.

Self-Check

"What if we added an index on start_date and end_date? How would that affect the time complexity?"