DELETE with WHERE condition in SQL - Time & Space Complexity

Time Complexity: DELETE with WHERE condition

O(n)

Understanding Time Complexity

When we delete rows from a database table using a condition, the database must find which rows match before removing them.

We want to understand how the time to delete grows as the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

DELETE FROM employees
WHERE department = 'Sales';

This code deletes all employees who work in the Sales department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning rows to check the department value.
• How many times: Once for each row in the table.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "Deleting with a WHERE condition is always very fast regardless of table size."

[OK] Correct: The database must check each row to see if it matches the condition, so bigger tables take more time.

Interview Connect

Understanding how delete operations scale helps you explain database performance clearly and shows you know what happens behind the scenes.

Self-Check

"What if the department column has an index? How would the time complexity change?"