DML (INSERT, UPDATE, DELETE) in DBMS Theory - Time & Space Complexity

Time Complexity: DML (INSERT, UPDATE, DELETE)

O(n)

Understanding Time Complexity

When working with database commands like INSERT, UPDATE, and DELETE, it's important to understand how the time to complete these actions changes as the amount of data grows.

We want to know: how does the work needed increase when we add more rows or update more records?

Scenario Under Consideration

Analyze the time complexity of the following SQL commands.

-- Insert multiple rows
INSERT INTO employees (name, age) VALUES ('Alice', 30), ('Bob', 25), ('Carol', 28);

-- Update rows matching a condition
UPDATE employees SET age = age + 1 WHERE department = 'Sales';

-- Delete rows matching a condition
DELETE FROM employees WHERE retired = TRUE;
    

These commands add new data, change existing data, or remove data based on conditions.

Identify Repeating Operations

Look at what repeats when these commands run.

• Primary operation: Scanning rows to find which ones to update or delete.
• How many times: Once for each row in the table or for each row inserted.

How Execution Grows With Input

As the number of rows in the table grows, the time to find and change rows grows too.

Input Size (n)	Approx. Operations
10	About 10 row checks or inserts
100	About 100 row checks or inserts
1000	About 1000 row checks or inserts

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

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the command grows linearly with the number of rows affected or checked.

Common Mistake

[X] Wrong: "Updating or deleting a few rows always takes the same time no matter how big the table is."

[OK] Correct: Even if only a few rows change, the database often needs to check many rows to find them, so time depends on table size.

Interview Connect

Understanding how data modification commands scale helps you explain database performance clearly and shows you know how data size affects work done.

Self-Check

"What if the table has an index on the column used in the WHERE clause? How would the time complexity change?"