URL maps for routing in GCP - Time & Space Complexity

Time Complexity: URL maps for routing

O(n)

Understanding Time Complexity

When using URL maps for routing in cloud infrastructure, it's important to understand how the routing decisions scale as the number of URL rules grows.

We want to know how the time to find the right route changes when more URL rules are added.

Scenario Under Consideration

Analyze the time complexity of the following URL map routing setup.

resource "google_compute_url_map" "example" {
  name = "example-url-map"

  default_service = google_compute_backend_service.default.self_link

  host_rule {
    hosts = ["example.com"]
    path_matcher = "path-matcher-1"
  }

  path_matcher {
    name = "path-matcher-1"
    default_service = google_compute_backend_service.default.self_link

    path_rule {
      paths = ["/images/*"]
      service = google_compute_backend_service.images.self_link
    }

    path_rule {
      paths = ["/videos/*"]
      service = google_compute_backend_service.videos.self_link
    }
  }
}
    

This configuration routes requests based on host and path rules to different backend services.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Matching incoming request paths against path rules in the URL map.
• How many times: Once per incoming request, checking each path rule until a match is found.

How Execution Grows With Input

As the number of path rules increases, the routing system checks more rules to find the correct backend.

Input Size (n)	Approx. Path Rules Checked
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows roughly in direct proportion to the number of path rules.

Final Time Complexity

Time Complexity: O(n)

This means the time to route a request grows linearly with the number of path rules to check.

Common Mistake

[X] Wrong: "Routing time stays the same no matter how many path rules exist."

[OK] Correct: Each additional path rule adds more checks, so routing takes longer as rules increase.

Interview Connect

Understanding how routing scales helps you design efficient URL maps and anticipate performance as your app grows.

Self-Check

"What if the URL map used a tree structure for path matching instead of a list? How would the time complexity change?"