Role-based access control (RBAC) in Apache Airflow - Time & Space Complexity

Time Complexity: Role-based access control (RBAC)

O(r * p)

Understanding Time Complexity

When using RBAC in Airflow, we want to know how the system handles permission checks as the number of users and roles grows.

We ask: How does the time to check access change when more roles or users are added?

Scenario Under Consideration

Analyze the time complexity of the following Airflow RBAC permission check code.

# Check if user has permission
user_roles = get_user_roles(user_id)  # returns list of roles
for role in user_roles:
    permissions = get_role_permissions(role)  # returns list of permissions
    if required_permission in permissions:
        return True
return False
    

This code checks if a user has a specific permission by looking through all their roles and the permissions each role grants.

Identify Repeating Operations

Look at what repeats in the code:

• Primary operation: Looping through each role the user has.
• How many times: Once for each role assigned to the user.
• Inside that, checking permissions for each role involves scanning the permissions list.
• The dominant work is scanning permissions for each role.

How Execution Grows With Input

As the number of roles and permissions grows, the checks take longer.

Input Size (n)	Approx. Operations
10 roles, 5 permissions each	~50 permission checks
100 roles, 10 permissions each	~1000 permission checks
1000 roles, 20 permissions each	~20,000 permission checks

Pattern observation: The total checks grow roughly by multiplying roles and permissions, so more roles or permissions means more work.

Final Time Complexity

Time Complexity: O(r * p)

This means the time to check permission grows with the number of roles (r) the user has times the number of permissions (p) each role contains.

Common Mistake

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

[OK] Correct: Because the code checks each role and its permissions one by one, more roles or permissions mean more checks, so time grows with input size.

Interview Connect

Understanding how permission checks scale helps you design systems that stay fast as users and roles grow. This skill shows you can think about real system limits and keep things running smoothly.

Self-Check

"What if permissions for each role were stored in a fast lookup like a set instead of a list? How would that change the time complexity?"