Fixed window algorithm in Rest API - Time & Space Complexity

Time Complexity: Fixed window algorithm

O(1)

Understanding Time Complexity

We want to understand how the time it takes to check and update request counts grows as more requests come in.

How does the fixed window algorithm handle many requests efficiently?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for fixed window rate limiting
function isRequestAllowed(userId) {
  currentWindow = getCurrentTime() / windowSize
  count = getCount(userId, currentWindow) // get count from storage
  if (count < limit) {
    incrementCount(userId, currentWindow)
    return true
  } else {
    return false
  }
}

This code checks if a user has made fewer requests than the limit in the current time window, then increments the count if allowed.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing and updating the count for the user in the current time window.
• How many times: Once per request received.

How Execution Grows With Input

Each request triggers a single check and update operation regardless of how many requests happened before.

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

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

Final Time Complexity

Time Complexity: O(1)

This means each request is handled in constant time, no matter how many requests have come before.

Common Mistake

[X] Wrong: "The time to check requests grows as more requests come in because we have to look at all previous requests."

[OK] Correct: The fixed window algorithm only checks the count for the current window, not all past requests, so it stays constant time.

Interview Connect

Understanding fixed window time complexity shows you can reason about how systems handle many requests efficiently, a useful skill for real-world API design.

Self-Check

"What if we changed the fixed window to a sliding window algorithm? How would the time complexity change?"