Batch update patterns in Rest API - Time & Space Complexity

Time Complexity: Batch update patterns

O(n)

Understanding Time Complexity

When updating many items at once using a batch update, it is important to understand how the time needed grows as the number of items increases.

We want to know how the total work changes when we update more records in one go.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

POST /api/items/batch-update
Request Body: { "items": [ {"id":1, "value":"A"}, {"id":2, "value":"B"}, ... ] }

// Server side pseudo-code
for item in request.items:
    update_database(item.id, item.value)
return success
    

This code updates each item in the batch one by one in the database.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each item to update it in the database.
• How many times: Once for every item in the batch.

How Execution Grows With Input

As the number of items to update grows, the total work grows in a similar way.

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

Pattern observation: Doubling the number of items roughly doubles the work needed.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the batch update grows directly in proportion to the number of items.

Common Mistake

[X] Wrong: "Batch updating many items is always constant time because it's one request."

[OK] Correct: Even though it's one request, the server still processes each item one by one, so time grows with the number of items.

Interview Connect

Understanding how batch updates scale helps you design efficient APIs and explain your choices clearly in interviews.

Self-Check

"What if the server used a single database query to update all items at once? How would the time complexity change?"