UPDATE with expressions in SQL - Time & Space Complexity

Time Complexity: UPDATE with expressions

O(n)

Understanding Time Complexity

When we update data in a table using expressions, it is important to know how the time to complete the update changes as the table grows.

We want to understand how the number of rows affects the work the database does during the update.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

UPDATE employees
SET salary = salary * 1.05
WHERE department = 'Sales';
    

This code increases the salary by 5% for all employees in the Sales department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database scans rows to find those in the Sales department.
• How many times: It checks each row once to see if it matches the condition, then updates matching rows.

How Execution Grows With Input

As the number of rows grows, the database must check more rows to find those to update.

Input Size (n)	Approx. Operations
10	About 10 checks and some updates
100	About 100 checks and more updates
1000	About 1000 checks and many updates

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

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the update grows linearly with the number of rows in the table.

Common Mistake

[X] Wrong: "The update only changes a few rows, so it runs in constant time."

[OK] Correct: Even if only a few rows are updated, the database still checks every row to find which ones to update, so the time grows with the table size.

Interview Connect

Understanding how updates scale helps you explain database behavior clearly and shows you can think about efficiency in real situations.

Self-Check

"What if we added an index on the department column? How would the time complexity change?"