Path-based routing in Kubernetes - Time & Space Complexity

Time Complexity: Path-based routing

O(n)

Understanding Time Complexity

We want to understand how the time to route requests changes as the number of paths grows in Kubernetes.

How does the system decide which backend to send a request to when many paths exist?

Scenario Under Consideration

Analyze the time complexity of the following Kubernetes Ingress path-based routing rules.

apiVersion: networking.k8s.io/v1
kind: Ingress
metadata:
  name: example-ingress
spec:
  rules:
  - http:
      paths:
      - path: /app1
        pathType: Prefix
        backend:
          service:
            name: app1-service
            port:
              number: 80
      - path: /app2
        pathType: Prefix
        backend:
          service:
            name: app2-service
            port:
              number: 80
      # ... more paths ...

This snippet routes incoming requests to different services based on the URL path prefix.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each path rule in order to find a match for the request path.
• How many times: The system may check up to all path rules (n) in the worst case.

How Execution Grows With Input

As the number of path rules increases, the system checks more paths one by one until it finds a match.

Input Size (n)	Approx. Operations
10	Up to 10 path checks
100	Up to 100 path checks
1000	Up to 1000 path checks

Pattern observation: The number of checks grows directly with the number of paths.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the right path grows linearly as you add more paths.

Common Mistake

[X] Wrong: "The routing time stays the same no matter how many paths exist."

[OK] Correct: Each new path adds a possible check, so more paths mean more work to find the match.

Interview Connect

Understanding how routing scales helps you design efficient systems and explain trade-offs clearly in real projects.

Self-Check

"What if the paths were stored in a tree structure instead of a list? How would the time complexity change?"