IN and NOT IN operators in MySQL - Time & Space Complexity

Time Complexity: IN and NOT IN operators

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run queries using IN and NOT IN changes as the list or table size grows.

How does the number of checks grow when we use these operators?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

SELECT * FROM employees
WHERE employee_id NOT IN (SELECT manager_id FROM managers);
    

The first query finds employees in certain departments using a fixed list. The second finds employees whose IDs are not in the managers list.

Identify Repeating Operations

Look for repeated checks or scans in the queries.

• Primary operation: Checking each employee against the list or subquery results.
• How many times: Once for each employee row in the table.

How Execution Grows With Input

As the number of employees grows, the database checks more rows against the list or subquery.

Input Size (n)	Approx. Operations
10	About 10 checks against the list or subquery
100	About 100 checks
1000	About 1000 checks

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the number of rows grows.

Common Mistake

[X] Wrong: "IN and NOT IN always run instantly no matter how big the list or table is."

[OK] Correct: The database must check each row against the list or subquery, so more rows mean more work.

Interview Connect

Understanding how IN and NOT IN scale helps you write queries that stay fast as data grows, a useful skill in real projects.

Self-Check

"What if the list inside IN was replaced by a large subquery returning thousands of values? How would the time complexity change?"