Time Complexity: WHERE with BETWEEN range
O(n)
0
0
WHERE with BETWEEN range in SQL - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time to run a SQL query changes when we use a WHERE clause with a BETWEEN range.
Specifically, how does the size of the data affect the time it takes to find rows within a range?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
SELECT *
FROM sales
WHERE sale_date BETWEEN '2023-01-01' AND '2023-01-31';
This query selects all sales records where the sale date is in January 2023.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Scanning rows to check if sale_date is within the given range.
- How many times: Once for each row in the sales table.
How Execution Grows With Input
As the number of rows in the sales table grows, the database must check more rows to find those in the date range.
| 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 run the query grows in a straight line as the table gets bigger.
Common Mistake
[X] Wrong: "Using BETWEEN always makes the query very fast regardless of table size."
[OK] Correct: Without an index, the database still checks every row, so bigger tables take longer.
Interview Connect
Understanding how filtering with ranges affects query time helps you explain how databases handle data efficiently.
Self-Check
"What if we added an index on sale_date? How would the time complexity change?"