Horizontal Pod Autoscaler in Kubernetes - Time & Space Complexity

Time Complexity: Horizontal Pod Autoscaler

O(n)

Understanding Time Complexity

We want to understand how the time it takes for the Horizontal Pod Autoscaler (HPA) to adjust pods changes as the number of pods or metrics grows.

How does the HPA's work scale when it checks and updates pods?

Scenario Under Consideration

Analyze the time complexity of the following Kubernetes Horizontal Pod Autoscaler configuration.

apiVersion: autoscaling/v2
kind: HorizontalPodAutoscaler
metadata:
  name: example-hpa
spec:
  scaleTargetRef:
    apiVersion: apps/v1
    kind: Deployment
    name: example-deployment
  minReplicas: 1
  maxReplicas: 10
  metrics:
  - type: Resource
    resource:
      name: cpu
      target:
        type: Utilization
        averageUtilization: 50

This HPA watches CPU usage and adjusts the number of pods between 1 and 10 based on average CPU utilization.

Identify Repeating Operations

The HPA controller regularly checks metrics and adjusts pods.

• Primary operation: Loop over all pods to get their CPU usage metrics.
• How many times: Once per check interval, for each pod in the deployment.

How Execution Grows With Input

As the number of pods increases, the HPA must check more metrics, so the work grows with the number of pods.

Input Size (pods)	Approx. Operations
10	10 metric checks
100	100 metric checks
1000	1000 metric checks

Pattern observation: The number of operations grows directly with the number of pods.

Final Time Complexity

Time Complexity: O(n)

This means the time to check and adjust pods grows linearly as the number of pods increases.

Common Mistake

[X] Wrong: "The HPA checks all pods instantly, so time does not grow with pod count."

[OK] Correct: Each pod's metrics must be checked individually, so more pods mean more work and longer checks.

Interview Connect

Understanding how autoscaling scales with workload size shows you can think about system efficiency and resource management, a key skill in real-world DevOps.

Self-Check

What if the HPA used aggregated metrics instead of per-pod metrics? How would the time complexity change?