Idempotency keys for safe retries in Rest API - Time & Space Complexity

Time Complexity: Idempotency keys for safe retries

O(1)

Understanding Time Complexity

When using idempotency keys in APIs, we want to know how the system handles repeated requests efficiently.

We ask: how does the time to process requests grow when retries happen?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for handling idempotent requests
function handleRequest(request) {
  if (cache.has(request.idempotencyKey)) {
    return cache.get(request.idempotencyKey);  // Return cached response
  }
  let response = processRequest(request);  // Process new request
  cache.set(request.idempotencyKey, response);  // Save response
  return response;
}
    

This code checks if a request with the same idempotency key was handled before. If yes, it returns the saved response. Otherwise, it processes the request and saves the result.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking and retrieving from the cache (usually a hash map or dictionary).
• How many times: Once per request, whether retry or new.

How Execution Grows With Input

As the number of unique idempotency keys grows, the cache size grows, but each lookup stays fast.

Input Size (n)	Approx. Operations
10	10 cache lookups, mostly fast
100	100 cache lookups, still fast
1000	1000 cache lookups, still fast

Pattern observation: Each request requires a single quick lookup, so time grows linearly with requests but each lookup is constant time.

Final Time Complexity

Time Complexity: O(1)

This means each request, including retries, is handled in constant time due to fast cache lookups.

Common Mistake

[X] Wrong: "Each retry causes the whole request to be processed again, so time grows with retries."

[OK] Correct: The idempotency key cache prevents reprocessing by returning saved results instantly, so retries do not add processing time.

Interview Connect

Understanding how idempotency keys keep retries efficient shows you grasp safe API design and performance, a valuable skill in real projects.

Self-Check

"What if the cache lookup was implemented as a list search instead of a hash map? How would the time complexity change?"