Subqueries with IN operator in MySQL - Time & Space Complexity

Time Complexity: Subqueries with IN operator

O(n)

Understanding Time Complexity

When using subqueries with the IN operator, it is important to understand how the query's running time changes as the data grows.

We want to know how the number of operations increases when the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_name
FROM employees
WHERE department_id IN (
  SELECT department_id
  FROM departments
  WHERE location = 'New York'
);
    

This query finds all employees who work in departments located in New York.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each employee, the database checks if their department_id is in the list returned by the subquery.
• How many times: This check happens once for every employee row.

How Execution Grows With Input

As the number of employees grows, the database must check more rows against the subquery results.

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

Pattern observation: The number of operations grows roughly in direct proportion to the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of employees.

Common Mistake

[X] Wrong: "The subquery runs once for each employee, so the time grows much faster than the number of employees."

[OK] Correct: The database usually runs the subquery once and reuses its results, so the main cost depends mostly on checking each employee against that list.

Interview Connect

Understanding how subqueries with IN work helps you explain query performance clearly and shows you can think about how data size affects speed.

Self-Check

"What if we changed the subquery to use EXISTS instead of IN? How would the time complexity change?"