Time Complexity: Role-based access
O(r * p)
0
0
Role-based access in MySQL - Time & Space Complexity
Understanding Time Complexity
When checking user permissions based on roles, the time it takes depends on how many roles and permissions exist.
We want to know how the work grows as the number of roles and permissions grows.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
SELECT p.permission_name
FROM permissions p
JOIN role_permissions rp ON p.permission_id = rp.permission_id
JOIN user_roles ur ON rp.role_id = ur.role_id
WHERE ur.user_id = ?;
This query finds all permissions for a user by joining user roles to role permissions and then to permissions.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Joining tables to find matching roles and permissions.
- How many times: For each role the user has, the query checks all permissions linked to that role.
How Execution Grows With Input
As the number of roles a user has and the number of permissions per role grow, the work grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 roles | Checks permissions for 10 roles |
| 100 roles | Checks permissions for 100 roles |
| 1000 roles | Checks permissions for 1000 roles |
Pattern observation: The work grows roughly in proportion to the number of roles and their permissions.
Final Time Complexity
Time Complexity: O(r * p)
This means the time grows with the number of roles (r) times the number of permissions per role (p).
Common Mistake
[X] Wrong: "The query time depends only on the number of users."
[OK] Correct: The query focuses on roles and permissions, so the number of users does not affect the time directly.
Interview Connect
Understanding how role-based access queries scale helps you design efficient permission checks in real applications.
Self-Check
"What if we added caching for user roles? How would the time complexity change?"