BETWEEN for range filtering in PostgreSQL - Time & Space Complexity

Time Complexity: BETWEEN for range filtering

O(n)

Understanding Time Complexity

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

We ask: How does the query speed change when the table gets bigger?

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 range.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of rows grows, the database checks more dates one by one.

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: "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.

Interview Connect

Understanding how range filters like BETWEEN scale 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?"