Last-Modified and If-Modified-Since in Rest API - Time & Space Complexity

Time Complexity: Last-Modified and If-Modified-Since

O(n)

Understanding Time Complexity

When a server uses Last-Modified and If-Modified-Since headers, it decides if it needs to send data again.

We want to see how the time to handle requests changes as more requests come in.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

GET /resource HTTP/1.1
Host: example.com
If-Modified-Since: Wed, 21 Oct 2015 07:28:00 GMT

// Server side:
if (resource.lastModified <= request.headers['If-Modified-Since']) {
  return 304 Not Modified;
} else {
  return 200 OK with resource data;
}

This code checks if the resource has changed since the time the client last saw it, to decide if data should be sent.

Identify Repeating Operations

• Primary operation: Comparing the resource's last modified timestamp with the request header.
• How many times: Once per incoming request.

How Execution Grows With Input

Each request requires a simple timestamp comparison, which takes the same small amount of time regardless of resource size.

Input Size (number of requests)	Approx. Operations
10	10 timestamp comparisons
100	100 timestamp comparisons
1000	1000 timestamp comparisons

Pattern observation: The work grows directly with the number of requests, but each check is very fast and simple.

Final Time Complexity

Time Complexity: O(n)

This means the time to handle requests grows linearly with the number of requests, with each request taking a quick check.

Common Mistake

[X] Wrong: "The server must read the whole resource file every time to check if it changed."

[OK] Correct: The server only compares timestamps, which is a quick check and does not require reading the full resource each time.

Interview Connect

Understanding how simple checks like timestamp comparisons scale helps you explain efficient server responses and caching in real projects.

Self-Check

"What if the server had to read the entire resource content to compare it each time? How would the time complexity change?"