server_name directive in Nginx - Time & Space Complexity

Time Complexity: server_name directive

O(1)

Understanding Time Complexity

We want to understand the time complexity of matching a server name in nginx.

How does nginx check the server_name directive when many names are configured?

Scenario Under Consideration

Analyze the time complexity of the following nginx configuration snippet.

server {
    listen 80;
    server_name example.com www.example.com api.example.com;

    location / {
        proxy_pass http://backend;
    }
}

This snippet defines a server block with three server names that nginx will match against incoming requests.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: nginx uses a hash table to look up the requested hostname against the configured server_names.
• How many times: Constant time operation regardless of list size.

How Execution Grows With Input

As the number of server names grows, nginx performs a constant-time hash lookup.

Input Size (n)	Approx. Operations
10	~1 hash lookup
100	~1 hash lookup
1000	~1 hash lookup

Pattern observation: The number of operations is constant regardless of the number of server names.

Final Time Complexity

Time Complexity: O(1)

This means the time to find a matching server name is constant, independent of how many names are listed, due to hashing.

Common Mistake

[X] Wrong: "nginx checks each server_name one by one, so more names mean more time."

[OK] Correct: nginx uses a hash table, enabling constant-time lookups.

Interview Connect

Understanding how nginx matches server names helps you explain how web servers handle requests efficiently.

Self-Check

"What if nginx used a linear list to store server names without hashing? How would the time complexity change?"