Access Control Lists (ACLs) in Operating Systems - Time & Space Complexity

Time Complexity: Access Control Lists (ACLs)

O(n)

Understanding Time Complexity

When working with Access Control Lists (ACLs), it is important to understand how the time to check permissions grows as the list gets longer.

We want to know how the system's work changes when more entries are added to the ACL.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function checkPermission(user, resource, acl) {
  for (const entry of acl) {
    if (entry.user == user && entry.resource == resource) {
      return entry.permission;
    }
  }
  return 'no access';
}
    

This code checks if a user has permission to access a resource by scanning through the ACL entries one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each ACL entry to find a matching user and resource.
• How many times: Up to once for each entry in the ACL list, until a match is found or the list ends.

How Execution Grows With Input

As the number of ACL entries grows, the time to check permissions grows roughly in direct proportion.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows linearly as the ACL list grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to check permissions increases directly with the number of ACL entries.

Common Mistake

[X] Wrong: "Checking permissions is always fast and constant time regardless of ACL size."

[OK] Correct: Because the code must look through each ACL entry until it finds a match, the time depends on how many entries there are.

Interview Connect

Understanding how permission checks scale with ACL size helps you design systems that remain efficient as they grow.

Self-Check

"What if the ACL was stored in a hash table instead of a list? How would the time complexity change?"