Capability-based security in Operating Systems - Time & Space Complexity

Time Complexity: Capability-based security

O(n)

Understanding Time Complexity

We want to understand how the time it takes to check permissions grows as the number of capabilities increases in a system using capability-based security.

Specifically, how does the system's work change when it verifies access rights for a user or process?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Check if a process has a capability
function hasCapability(process, capability) {
  for (let cap of process.capabilities) {
    if (cap === capability) {
      return true;
    }
  }
  return false;
}
    

This code checks if a process holds a specific capability by scanning through its list of capabilities.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through the list of capabilities held by the process.
• How many times: Up to once for each capability until the desired one is found or the list ends.

How Execution Grows With Input

As the number of capabilities a process has grows, the time to check for one capability 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 time grows linearly as the number of capabilities increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to check a capability grows directly with the number of capabilities the process has.

Common Mistake

[X] Wrong: "Checking a capability always takes the same amount of time no matter how many capabilities there are."

[OK] Correct: Because the code must look through the list until it finds the capability or reaches the end, so more capabilities mean more work.

Interview Connect

Understanding how capability checks scale helps you design secure systems that remain efficient as they grow.

Self-Check

"What if the capabilities were stored in a data structure that allows instant lookup? How would the time complexity change?"