BETWEEN range filtering in MySQL - Time & Space Complexity

Time Complexity: BETWEEN range filtering

O(n)

Understanding Time Complexity

When we use BETWEEN to filter data in a database, we want to know how the time to find matching rows changes as the data grows.

We ask: How does the number of rows affect the time it takes to filter with BETWEEN?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM orders
WHERE order_date BETWEEN '2023-01-01' AND '2023-01-31';
    

This query selects all orders placed in January 2023 by checking if the order_date falls within the given date range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row's order_date to see if it falls in the date range.
• How many times: Once for every row in the orders table.

How Execution Grows With Input

As the number of rows grows, the database checks more rows to find matches.

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

Pattern observation: The number of checks grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to filter grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "BETWEEN instantly finds the rows without checking many entries."

[OK] Correct: Without an index, the database must look at each row to see if it fits the range, so it takes longer as data grows.

Interview Connect

Understanding how filtering with BETWEEN scales helps you explain query performance clearly and shows you know how databases handle data.

Self-Check

"What if we add an index on order_date? How would the time complexity change?"