Ingress resource definition in Kubernetes - Time & Space Complexity

Time Complexity: Ingress resource definition

O(n)

Understanding Time Complexity

We want to understand how the time to process an Ingress resource changes as it grows.

Specifically, how does adding more rules affect the work Kubernetes does?

Scenario Under Consideration

Analyze the time complexity of the following Ingress resource definition.

apiVersion: networking.k8s.io/v1
kind: Ingress
metadata:
  name: example-ingress
spec:
  rules:
  - host: example.com
    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

This Ingress routes requests to different services based on URL paths.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Kubernetes checks each path rule in the Ingress to find a match for incoming requests.
• How many times: It examines each path rule one by one until it finds a match or finishes all rules.

How Execution Grows With Input

As the number of path rules increases, the time to find the right backend grows roughly in a straight line.

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

Pattern observation: The work grows directly with the number of path rules.

Final Time Complexity

Time Complexity: O(n)

This means the time to process the Ingress grows linearly with the number of path rules.

Common Mistake

[X] Wrong: "Adding more path rules won't affect performance because Kubernetes handles all paths instantly."

[OK] Correct: Kubernetes must check each path rule to find a match, so more rules mean more checks and more time.

Interview Connect

Understanding how resource size affects processing time helps you design scalable Kubernetes configurations and shows you think about system behavior beyond just writing code.

Self-Check

"What if the Ingress used a more efficient matching method like a prefix tree? How would the time complexity change?"