Rate limit error responses in Rest API - Time & Space Complexity

Time Complexity: Rate limit error responses

O(n)

Understanding Time Complexity

When a server limits how many requests you can send, it must check each request against the limit.

We want to know how the time to check changes as more requests come in.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for rate limit check
function checkRateLimit(userId) {
  const requests = getRequestsForUser(userId);
  const now = currentTime();
  const windowStart = now - timeWindow;
  const recentRequests = requests.filter(r => r.timestamp >= windowStart);
  if (recentRequests.length > maxAllowed) {
    return errorResponse("Rate limit exceeded");
  }
  return successResponse();
}
    

This code checks how many requests a user made recently and returns an error if they went over the limit.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Filtering the user's request list to find recent requests.
• How many times: Once per check, but the filter checks each past request in the list.

How Execution Grows With Input

As the number of past requests grows, the filter checks more items each time.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to check grows in a straight line with how many past requests there are.

Common Mistake

[X] Wrong: "The rate limit check is always fast and constant time."

[OK] Correct: Because it looks at all past requests, more requests mean more work, so it can slow down.

Interview Connect

Understanding how checking rate limits scales helps you design APIs that stay fast even with many users.

Self-Check

"What if we stored only the count of requests in the time window instead of all timestamps? How would the time complexity change?"