Request/response transformation in Nginx - Time & Space Complexity

Time Complexity: Request/response transformation

O(n)

Understanding Time Complexity

When nginx changes requests or responses, it does some work for each request it handles.

We want to know how this work grows as more requests come in or as the data changes.

Scenario Under Consideration

Analyze the time complexity of the following nginx configuration snippet.

server {
    listen 80;
    location / {
        proxy_pass http://backend;
        proxy_set_header Host $host;
        sub_filter 'foo' 'bar';
        sub_filter_once off;
    }
}
    

This snippet forwards requests to a backend and replaces all occurrences of 'foo' with 'bar' in the response.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the entire response body to find and replace all 'foo' strings.
• How many times: Once per response, for every byte in the response body.

How Execution Grows With Input

The time to transform the response grows as the response size grows because nginx checks each part of the response.

Input Size (n) - response bytes	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The work grows directly with the size of the response.

Final Time Complexity

Time Complexity: O(n)

This means the time to transform the response grows linearly with the response size.

Common Mistake

[X] Wrong: "The transformation time stays the same no matter how big the response is."

[OK] Correct: Because nginx must check every part of the response to find all matches, bigger responses take more time.

Interview Connect

Understanding how request and response transformations scale helps you explain performance impacts clearly and shows you think about real-world server behavior.

Self-Check

"What if nginx only replaced the first occurrence of 'foo' instead of all? How would the time complexity change?"