Time Complexity: GRANT and REVOKE permissions
O(n * m)
0
0
GRANT and REVOKE permissions in PostgreSQL - Time & Space Complexity
Understanding Time Complexity
When we give or take away permissions in a database, it takes some time to process. We want to understand how this time changes when we have more users or more permissions.
How does the time to grant or revoke permissions grow as the number of users or permissions increases?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
GRANT SELECT, INSERT ON employees TO user1;
REVOKE INSERT ON employees FROM user1;
GRANT UPDATE ON employees TO user2;
REVOKE ALL ON employees FROM user3;
-- Grant or revoke permissions for multiple users
GRANT SELECT ON employees TO user1, user2, user3;
This code gives or removes permissions on the "employees" table for different users.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Applying permission changes for each user and each permission.
- How many times: Once per user-permission pair in the command.
How Execution Grows With Input
When you add more users or more permissions in one command, the work grows because the database must update each user's permissions separately.
| Input Size (n users x m permissions) | Approx. Operations |
|---|---|
| 10 users x 2 permissions | 20 permission changes |
| 100 users x 3 permissions | 300 permission changes |
| 1000 users x 5 permissions | 5000 permission changes |
Pattern observation: The total work grows roughly by multiplying the number of users by the number of permissions.
Final Time Complexity
Time Complexity: O(n * m)
This means the time to grant or revoke permissions grows in proportion to the number of users times the number of permissions involved.
Common Mistake
[X] Wrong: "Granting permissions to many users at once takes the same time as granting to one user."
[OK] Correct: The database must update each user's permissions separately, so more users mean more work and more time.
Interview Connect
Understanding how permission changes scale helps you design systems that manage access efficiently and avoid slowdowns when many users are involved.
Self-Check
"What if we grant permissions to a role instead of individual users? How would the time complexity change?"