Pod affinity and anti-affinity in Kubernetes - Time & Space Complexity

Time Complexity: Pod affinity and anti-affinity

O(n)

Understanding Time Complexity

When Kubernetes schedules pods, it checks rules like pod affinity and anti-affinity to decide where pods should run.

We want to understand how the time to make these decisions grows as the number of pods and nodes increases.

Scenario Under Consideration

Analyze the time complexity of this pod scheduling snippet with affinity rules.

apiVersion: v1
kind: Pod
metadata:
  name: example-pod
spec:
  affinity:
    podAffinity:
      requiredDuringSchedulingIgnoredDuringExecution:
      - labelSelector:
          matchExpressions:
          - key: security
            operator: In
            values:
            - S1
        topologyKey: kubernetes.io/hostname
  containers:
  - name: nginx
    image: nginx

This pod requests to be scheduled on a node where pods with label "security: S1" already run on the same hostname.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking all existing pods on all nodes to find matches for affinity rules.
• How many times: For each node, the scheduler scans pods running there to verify label matches.

How Execution Grows With Input

As the number of nodes and pods grows, the scheduler must check more pods per node to satisfy affinity rules.

Input Size (n)	Approx. Operations
10 nodes, 50 pods	Checks pods on each node, about 50 checks total
100 nodes, 500 pods	Checks increase roughly 10 times, about 500 checks
1000 nodes, 5000 pods	Checks increase roughly 100 times, about 5000 checks

Pattern observation: The number of checks grows roughly linearly with the total number of pods across nodes.

Final Time Complexity

Time Complexity: O(n)

This means the scheduling time grows roughly in direct proportion to the number of pods the scheduler must check for affinity.

Common Mistake

[X] Wrong: "The scheduler only checks one node or a fixed small number of pods regardless of cluster size."

[OK] Correct: The scheduler must evaluate all nodes and pods to find a suitable place, so the work grows with cluster size.

Interview Connect

Understanding how pod affinity affects scheduling time helps you explain real cluster behavior and scalability in interviews.

Self-Check

What if we changed requiredDuringSchedulingIgnoredDuringExecution to preferredDuringSchedulingIgnoredDuringExecution? How would the time complexity change?