WHERE with IN list in SQL - Time & Space Complexity

Time Complexity: WHERE with IN list

O(n * m)

Understanding Time Complexity

We want to understand how the time to run a SQL query changes when using a WHERE clause with an IN list.

Specifically, how does the number of values inside the IN list affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM employees
WHERE department_id IN (10, 20, 30, 40, 50);
    

This query selects all employees who belong to any of the listed departments.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row's department_id against the IN list values.
• How many times: Once for each row in the employees table.

How Execution Grows With Input

As the number of rows grows, the database checks more rows. Also, as the IN list grows, each check takes longer.

Input Size (rows)	IN List Size	Approx. Operations
10	5	About 50 checks (10 rows x 5 values)
100	5	About 500 checks
1000	5	About 5000 checks

Pattern observation: The total checks grow with both the number of rows and the size of the IN list.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows with the number of rows (n) times the number of values in the IN list (m).

Common Mistake

[X] Wrong: "The IN list size does not affect performance because it's just a simple check."

[OK] Correct: Each value in the IN list is checked against every row, so a bigger list means more checks and more work.

Interview Connect

Understanding how the IN list size affects query time helps you write efficient queries and explain your reasoning clearly in interviews.

Self-Check

"What if the IN list is replaced by a subquery that returns many values? How would the time complexity change?"