Policy evaluation logic in AWS - Time & Space Complexity

Time Complexity: Policy evaluation logic

O(n)

Understanding Time Complexity

When AWS checks if a user can do something, it looks at policies. Understanding how long this check takes helps us know how fast permissions work.

We want to see how the time to decide permission changes as we add more policies or rules.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

// Simplified policy evaluation logic
for each policy attached to user or resource {
  for each statement in policy {
    if statement matches action and resource {
      evaluate allow or deny
    }
  }
}
return final decision
    

This sequence checks all policies and their statements to decide if an action is allowed or denied.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Checking each statement in every policy attached to the user or resource.
• How many times: Once for each statement in each policy.

How Execution Grows With Input

As you add more policies or statements, the number of checks grows. More policies mean more statements to look through.

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

Pattern observation: The time grows directly with the number of statements checked.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide permissions grows in a straight line as you add more policy statements.

Common Mistake

[X] Wrong: "Adding more policies won't slow down permission checks much because AWS is super fast."

[OK] Correct: Each policy statement must be checked, so more statements mean more work and more time.

Interview Connect

Understanding how permission checks grow helps you design better systems and explain your thinking clearly in interviews.

Self-Check

"What if policies had nested conditions that require extra checks? How would the time complexity change?"