Sentinel policy as code in Terraform - Time & Space Complexity

Time Complexity: Sentinel policy as code

O(n)

Understanding Time Complexity

We want to understand how the time to check policies grows as we add more rules or resources.

How does the number of policy checks change when the input grows?

Scenario Under Consideration

Analyze the time complexity of this Sentinel policy check in Terraform.

policy "example" {
  rule "check_tags" {
    all resources as r {
      r.tags contains "environment"
    }
  }
}
    

This policy checks that every resource has an "environment" tag.

Identify Repeating Operations

Look at what repeats when the policy runs.

• Primary operation: Checking each resource's tags for the "environment" key.
• How many times: Once for every resource in the plan.

How Execution Grows With Input

As the number of resources grows, the number of checks grows too.

Input Size (n)	Approx. API Calls/Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The checks grow directly with the number of resources.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the policy grows in a straight line as you add more resources.

Common Mistake

[X] Wrong: "The policy runs in the same time no matter how many resources there are."

[OK] Correct: Each resource needs to be checked, so more resources mean more work.

Interview Connect

Understanding how policy checks scale helps you design efficient rules and predict performance as infrastructure grows.

Self-Check

"What if the policy checked every tag on every resource instead of just one tag? How would the time complexity change?"