Prefix match in Nginx - Time & Space Complexity

Time Complexity: Prefix match

O(n)

Understanding Time Complexity

We want to understand how the time to find a prefix match in nginx changes as the number of prefixes grows.

How does nginx handle many prefix rules efficiently?

Scenario Under Consideration

Analyze the time complexity of the following nginx prefix match configuration.

location /images/ {
    # serve images
}
location /images/thumbnails/ {
    # serve thumbnails
}
location /images/icons/ {
    # serve icons
}

This snippet shows multiple prefix locations nginx checks to find the best match for a request URL.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: nginx compares the request URI against each prefix location.
• How many times: It checks prefixes one by one until it finds the longest matching prefix.

How Execution Grows With Input

As the number of prefix locations increases, nginx must check more prefixes to find the best match.

Input Size (n)	Approx. Operations
10	About 10 prefix checks
100	About 100 prefix checks
1000	About 1000 prefix checks

Pattern observation: The number of checks grows linearly with the number of prefix locations.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a prefix match grows directly with how many prefix rules there are.

Common Mistake

[X] Wrong: "nginx finds prefix matches instantly no matter how many prefixes exist."

[OK] Correct: nginx checks prefixes one by one, so more prefixes mean more checks and longer time.

Interview Connect

Understanding how prefix matching scales helps you explain real-world server behavior clearly and confidently.

Self-Check

"What if nginx used a tree structure to store prefixes? How would the time complexity change?"