Content negotiation in Rest API - Time & Space Complexity

Time Complexity: Content negotiation

O(n * m)

Understanding Time Complexity

When a server chooses the best format to send data based on what a client asks for, it uses content negotiation.

We want to know how the time to decide the format changes as the number of supported formats grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function negotiateContentType(acceptHeader, supportedTypes) {
  for (const type of supportedTypes) {
    if (acceptHeader.includes(type)) {
      return type;
    }
  }
  return supportedTypes[0];
}

This code checks each supported type to find one that matches the client's Accept header and returns it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list of supported content types.
• How many times: Up to once for each supported type until a match is found.

How Execution Grows With Input

As the number of supported types grows, the code may check more items before finding a match or giving up.

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

Pattern observation: The number of checks grows directly with the number of supported types.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to find a matching content type grows linearly with the number of supported types and the length of the Accept header string.

Common Mistake

[X] Wrong: "The server checks all supported types every time, so it always takes the same long time."

[OK] Correct: The server stops checking as soon as it finds a match, so sometimes it finishes quickly.

Interview Connect

Understanding how content negotiation scales helps you explain how servers handle different client needs efficiently.

Self-Check

"What if the supported types were stored in a set instead of a list? How would the time complexity change?"