Time Complexity: Access control matrix
O(k)
0
0
Access control matrix in Operating Systems - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time to check permissions grows as the number of users and resources increases in an access control matrix.
How does the system's work change when more users or resources are added?
Scenario Under Consideration
Analyze the time complexity of the following access check operation.
// Access Control Matrix check
function checkAccess(user, resource, operation) {
if (matrix[user] && matrix[user][resource]) {
return matrix[user][resource].includes(operation);
}
return false;
}
This code checks if a user has permission to perform an operation on a resource by looking up the matrix.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Checking if the operation exists in the list of permissions for the user-resource pair.
- How many times: The includes() method scans the list of permissions, which depends on the number of operations allowed for that resource.
How Execution Grows With Input
As the number of users and resources grows, the lookup remains direct, but the time to check permissions depends on how many operations are listed.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 operations | 10 checks in the permission list |
| 100 operations | 100 checks in the permission list |
| 1000 operations | 1000 checks in the permission list |
Pattern observation: The time grows linearly with the number of operations allowed per resource for a user.
Final Time Complexity
Time Complexity: O(k)
This means the time to check access grows linearly with the number of permissions listed for that user-resource pair.
Common Mistake
[X] Wrong: "Checking access takes constant time no matter how many permissions exist."
[OK] Correct: Because the code scans the list of permissions, more permissions mean more checks, so time grows with the list size.
Interview Connect
Understanding how permission checks scale helps you design systems that stay fast even as users and resources grow.
Self-Check
"What if the permissions were stored in a hash set instead of a list? How would the time complexity change?"