ETag for conditional requests in Rest API - Time & Space Complexity

Time Complexity: ETag for conditional requests

O(n)

Understanding Time Complexity

When using ETags for conditional requests, we want to understand how the server's work changes as the number of requests or resources grows.

How does the server's processing time grow when checking ETags for many requests?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for handling a conditional GET request with ETag
function handleRequest(request) {
  resource = getResource(request.url)
  clientETag = request.headers['If-None-Match']
  serverETag = generateETag(resource)

  if (clientETag === serverETag) {
    return 304; // Not Modified
  } else {
    return 200; // OK with resource
  }
}
    

This code checks if the client's ETag matches the server's current ETag for a resource to decide if the full data needs to be sent.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Generating the ETag for the requested resource.
• How many times: Once per request, for each resource requested.

How Execution Grows With Input

Each request requires generating an ETag, which depends on the resource size.

Input Size (resource size)	Approx. Operations
Small (10 KB)	Low operations to hash or check content
Medium (100 KB)	More operations, roughly 10 times more than small
Large (1 MB)	Much more operations, about 100 times more than small

Pattern observation: The time to generate an ETag grows roughly in proportion to the size of the resource.

Final Time Complexity

Time Complexity: O(n)

This means the time to process a request grows linearly with the size of the resource being checked.

Common Mistake

[X] Wrong: "ETag checking is always instant and does not depend on resource size."

[OK] Correct: Generating or verifying an ETag often requires reading or hashing the resource, which takes more time for bigger resources.

Interview Connect

Understanding how ETag checks scale helps you explain efficient caching strategies and server load management in real projects.

Self-Check

"What if the server cached ETags instead of generating them on every request? How would the time complexity change?"