ANY and ALL with arrays in PostgreSQL - Time & Space Complexity

Time Complexity: ANY and ALL with arrays

O(n)

Understanding Time Complexity

When using ANY and ALL with arrays in PostgreSQL, it's important to understand how the query time grows as the array size increases.

We want to know how many checks the database does when comparing values against array elements.

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL query using ANY and ALL with arrays.

SELECT * FROM products
WHERE price > ANY (ARRAY[10, 20, 30]);

SELECT * FROM products
WHERE price < ALL (ARRAY[100, 200, 300]);
    

This code checks if the product price is greater than any value in the array or less than all values in the array.

Identify Repeating Operations

Look at what repeats when the query runs:

• Primary operation: Comparing the column value against each element in the array.
• How many times: Once for each element in the array.

How Execution Grows With Input

As the array size grows, the number of comparisons grows too.

Input Size (n)	Approx. Operations
3	3 comparisons
10	10 comparisons
100	100 comparisons

Pattern observation: The number of comparisons grows directly with the array size.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of elements in the array.

Common Mistake

[X] Wrong: "ANY and ALL check all array elements instantly regardless of size."

[OK] Correct: The database compares each element one by one until it finds a match or finishes checking, so more elements mean more work.

Interview Connect

Understanding how ANY and ALL work with arrays helps you explain query performance clearly and shows you know how databases handle comparisons internally.

Self-Check

"What if the array was replaced by a subquery returning many rows? How would the time complexity change?"