UPDATE with subquery preview in SQL - Time & Space Complexity

Time Complexity: UPDATE with subquery preview

O(n)

Understanding Time Complexity

When we update data using a subquery, the database must find matching rows before changing values.

We want to know how the work grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

UPDATE employees
SET salary = salary * 1.1
WHERE department_id IN (
  SELECT department_id
  FROM departments
  WHERE location = 'New York'
);
    

This code increases salaries by 10% for employees in departments located in New York.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each employee to see if their department matches one from the subquery.
• How many times: Once for each employee row in the table.

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
100	About 100 checks
1000	About 1000 checks

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

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The subquery runs once and does not affect the update time much."

[OK] Correct: The subquery results must be matched against each employee, so its size and complexity impact the total work.

Interview Connect

Understanding how updates with subqueries scale helps you write efficient queries and explain your reasoning clearly.

Self-Check

"What if the subquery returned a very large list of department IDs? How would that affect the time complexity?"