Nested subqueries in SQL - Time & Space Complexity

Time Complexity: Nested subqueries

O(n * m)

Understanding Time Complexity

When using nested subqueries, it is important to understand how the work grows as the data gets bigger.

We want to know how many times the database repeats tasks inside these nested queries.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT employee_id, name
FROM employees
WHERE department_id IN (
  SELECT department_id
  FROM departments
  WHERE location_id = 100
);

This query finds employees who work in departments located at a specific location.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The inner subquery scans the departments table once.
• How many times: The outer query scans the employees table once, then checks each employee's department against the subquery result.

How Execution Grows With Input

As the number of employees and departments grows, the database does more work to match employees to departments.

Input Size (n)	Approx. Operations
10 employees, 5 departments	About 10 checks against 5 departments
100 employees, 50 departments	About 100 checks against 50 departments
1000 employees, 500 departments	About 1000 checks against 500 departments

Pattern observation: The work grows roughly by multiplying the number of employees by the number of departments.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows by multiplying the size of the outer table by the size of the inner table.

Common Mistake

[X] Wrong: "The inner subquery runs only once, so the time is just O(n)."

[OK] Correct: The inner subquery result is used for each row in the outer query, so the total work depends on both tables.

Interview Connect

Understanding how nested subqueries affect performance helps you write better queries and explain your choices clearly.

Self-Check

"What if we replaced the IN subquery with a JOIN? How would the time complexity change?"