Time Complexity: Exact match (=)
O(n)
0
0
Exact match (=) in Nginx - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes for nginx to find an exact match in its configuration grows as the number of rules increases.
Specifically, how does nginx check for an exact match when processing requests?
Scenario Under Consideration
Analyze the time complexity of the following nginx exact match configuration snippet.
location = /about {
return 200 "About page";
}
location = /contact {
return 200 "Contact page";
}
location / {
return 404;
}
This snippet defines exact match locations for "/about" and "/contact" URLs, and a default catch-all location.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: nginx checks each exact match location one by one to find a matching URL.
- How many times: It compares the request URI against each exact match rule until it finds a match or exhausts all.
How Execution Grows With Input
As the number of exact match locations grows, nginx must check more rules one after another.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Up to 10 string comparisons |
| 100 | Up to 100 string comparisons |
| 1000 | Up to 1000 string comparisons |
Pattern observation: The number of checks grows directly with the number of exact match rules.
Final Time Complexity
Time Complexity: O(n)
This means the time to find an exact match grows linearly as you add more exact match locations.
Common Mistake
[X] Wrong: "nginx finds exact matches instantly no matter how many rules there are."
[OK] Correct: nginx checks exact matches one by one, so more rules mean more checks and longer time.
Interview Connect
Understanding how nginx processes exact matches helps you reason about request handling speed and configuration design in real projects.
Self-Check
"What if nginx used a hash table for exact matches? How would the time complexity change?"