Async batch processing in Rest API - Time & Space Complexity

Time Complexity: Async batch processing

O(n)

Understanding Time Complexity

When working with async batch processing, it is important to understand how the time to complete tasks grows as the number of items increases.

We want to know how the total time changes when processing many requests in batches asynchronously.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

async function processBatch(items) {
  const batchSize = 5;
  for (let i = 0; i < items.length; i += batchSize) {
    const batch = items.slice(i, i + batchSize);
    await Promise.all(batch.map(item => processItem(item)));
  }
}

This code processes items in batches of 5, running each batch's items asynchronously, waiting for all to finish before moving to the next batch.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over items in batches and processing each batch asynchronously.
• How many times: The loop runs about n / batchSize times, where n is the number of items.

How Execution Grows With Input

As the number of items grows, the number of batches grows roughly in proportion.

Input Size (n)	Approx. Operations
10	2 batches of 5 items each
100	20 batches of 5 items each
1000	200 batches of 5 items each

Pattern observation: The total number of batches grows linearly with input size, so total work grows steadily as more items are added.

Final Time Complexity

Time Complexity: O(n)

This means the total time to process all items grows roughly in direct proportion to the number of items.

Common Mistake

[X] Wrong: "Because items are processed asynchronously in batches, the total time stays the same no matter how many items there are."

[OK] Correct: Even though items in a batch run at the same time, batches run one after another, so total time still grows with the number of batches, which depends on total items.

Interview Connect

Understanding how async batch processing scales helps you explain how to handle many requests efficiently and shows you can reason about real-world code performance.

Self-Check

"What if we processed all items fully in parallel without batching? How would the time complexity change?"