Role-based access control in GraphQL - Time & Space Complexity

Time Complexity: Role-based access control

O(r x p)

Understanding Time Complexity

When checking user permissions in role-based access control, we want to know how the time to verify access changes as the number of roles or users grows.

We ask: How does the system's work increase when more roles or users are involved?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

query GetUserPermissions($userId: ID!) {
  user(id: $userId) {
    roles {
      permissions {
        name
      }
    }
  }
}
    

This query fetches a user's roles and the permissions each role grants.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the list of roles and then the list of permissions for each role.
• How many times: Once for each role, and inside that, once for each permission of that role.

How Execution Grows With Input

As the number of roles (r) and permissions per role (p) increase, the total checks grow by multiplying these counts.

Input Size (roles x permissions)	Approx. Operations
10 roles x 5 permissions	50
100 roles x 5 permissions	500
100 roles x 20 permissions	2000

Pattern observation: The work grows roughly by multiplying the number of roles by the number of permissions per role.

Final Time Complexity

Time Complexity: O(r × p)

This means the time to check permissions grows in proportion to the number of roles times the permissions each role has.

Common Mistake

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

[OK] Correct: The system must look through each role and its permissions, so more roles or permissions mean more work.

Interview Connect

Understanding how permission checks scale helps you design systems that stay quick even as users and roles grow. This skill shows you can think about real-world system performance.

Self-Check

"What if we cached permissions per user instead of checking roles each time? How would the time complexity change?"