Access control matrix in Operating Systems - Time & Space Complexity

Time Complexity: Access control matrix

O(k)

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?"

Practice

1. What does an access control matrix primarily represent in operating systems?

easy

A. Which users have what permissions on which resources

B. The order in which processes are executed

C. The memory allocation for each program

D. The list of installed software on a system

Solution

1. Step 1: Understand the purpose of access control matrix

   An access control matrix is a table that shows permissions users have on resources.

2. Step 2: Match the description to the options

   Only Which users have what permissions on which resources correctly describes permissions of users on resources.

3. Final Answer:

   Which users have what permissions on which resources -> Option A

4. Quick Check:

   Access control matrix = user permissions on resources [OK]

Hint: Think: Who can do what on which resource? [OK]

Common Mistakes:

• Confusing access control matrix with process scheduling
• Thinking it shows memory or software lists
• Mixing permissions with system hardware details

2. Which of the following correctly represents a row in an access control matrix?

easy

A. Process1 -> Memory address 0x1000

B. User1: read, write

C. File size = 1024 bytes

D. CPU usage = 50%

Solution

1. Step 1: Identify what a row in access control matrix shows

   A row lists a user and their permissions on various resources.

2. Step 2: Check which option matches this format

   User1: read, write shows a user with permissions, matching the row concept.

3. Final Answer:

   User1: read, write -> Option B

4. Quick Check:

   Row = user permissions list [OK]

Hint: Rows list users and their permissions [OK]

Common Mistakes:

• Confusing resource details with user permissions
• Mixing process or CPU info with access control
• Choosing options unrelated to permissions

3. Given the access control matrix below:

Users\Files | File1 | File2
---------|--------|-------
Alice | read | write
Bob | write | execute

What permission does Bob have on File2?

medium

A. execute

B. write

C. read

D. no permission

Solution

1. Step 1: Locate Bob's row in the matrix

   Bob's permissions are listed in the second row.

2. Step 2: Find the permission under File2 column for Bob

   Bob has 'execute' permission on File2.

3. Final Answer:

   execute -> Option A

4. Quick Check:

   Bob on File2 = execute [OK]

Hint: Find user row, then resource column [OK]

Common Mistakes:

• Mixing up rows and columns
• Choosing Alice's permissions instead of Bob's
• Assuming default permissions if not listed

4. Identify the error in this access control matrix snippet:

Users\Resources | FileA | FileB
--------------|--------|-------
Carol | read | readwriteexecute

What is wrong with this matrix?

medium

A. The matrix must list users vertically, not horizontally

B. Carol cannot have read permission

C. Multiple permissions should be separated, not combined in one cell

D. FileB should not have any permissions listed

Solution

1. Step 1: Check how permissions are listed in each cell

   Permissions should be clearly separated, usually by commas or listed distinctly.

2. Step 2: Identify if combining multiple permissions in one cell is acceptable

   Combining multiple permissions in one cell without clear separation can cause confusion.

3. Final Answer:

   Multiple permissions should be separated, not combined in one cell -> Option C

4. Quick Check:

   Permissions must be clearly separated [OK]

Hint: Permissions must be clearly separated in matrix cells [OK]

Common Mistakes:

• Thinking users must be listed horizontally
• Assuming permissions can't be combined at all
• Ignoring formatting clarity in matrix

5. You have an access control matrix with users and resources. If you want to quickly check which users can write to a resource named Report.doc, what is the best approach?

hard

A. Look across the row for Report.doc and note users with write permission

B. Check the entire matrix for any write permission

C. Check the diagonal cells only for write permission

D. Look down the column for Report.doc and note users with write permission

Solution

1. Step 1: Understand matrix layout

   Rows represent users, columns represent resources.

2. Step 2: To find users who can write to Report.doc, check the column for that resource

   Looking down the column shows which users have write permission.

3. Final Answer:

   Look down the column for Report.doc and note users with write permission -> Option D

4. Quick Check:

   Users with write on resource = column check [OK]

Hint: Check down the resource column for permissions [OK]

Common Mistakes:

• Looking across a resource row instead of column
• Checking only diagonal cells
• Scanning entire matrix unnecessarily