Cache-Control header directives in Rest API - Time & Space Complexity

Time Complexity: Cache-Control header directives

O(n)

Understanding Time Complexity

When working with Cache-Control headers in REST APIs, it's important to understand how the processing time changes as the number of directives grows.

We want to know how the time to parse and apply these directives scales with input size.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function parseCacheControl(header) {
  const directives = header.split(",");
  const result = {};
  for (const directive of directives) {
    const [key, value] = directive.trim().split("=");
    result[key] = value || true;
  }
  return result;
}
    

This code splits the Cache-Control header string into directives and parses each into a key-value pair.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each directive in the header string.
• How many times: Once for each directive found after splitting by commas.

How Execution Grows With Input

The time to parse grows directly with the number of directives in the header.

Input Size (n)	Approx. Operations
10	About 10 loops and splits
100	About 100 loops and splits
1000	About 1000 loops and splits

Pattern observation: The work increases evenly as the number of directives increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to parse Cache-Control directives grows linearly with the number of directives.

Common Mistake

[X] Wrong: "Parsing Cache-Control headers takes constant time no matter how many directives there are."

[OK] Correct: Each directive must be processed individually, so more directives mean more work.

Interview Connect

Understanding how parsing headers scales helps you write efficient API code and shows you can think about performance in real-world tasks.

Self-Check

"What if the header string was already split into an array before parsing? How would that affect the time complexity?"