Fine-grained access control in DynamoDB - Time & Space Complexity

Time Complexity: Fine-grained access control

O(n)

Understanding Time Complexity

When using fine-grained access control in DynamoDB, we want to know how the time to check permissions grows as data or rules increase.

We ask: How does the cost of enforcing detailed access rules change with more data or conditions?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB policy check snippet.

// Example: Checking user access to items with attribute filters
const params = {
  TableName: "Documents",
  KeyConditionExpression: "UserId = :uid",
  FilterExpression: "AccessLevel = :level",
  ExpressionAttributeValues: {
    ":uid": userId,
    ":level": userAccessLevel
  }
};
const result = await dynamodb.query(params).promise();
// Returns items user can access based on fine-grained rules

This code queries items for a user and filters them by access level to enforce fine-grained control.

Identify Repeating Operations

Look for repeated work in the query and filtering process.

• Primary operation: Querying items matching user ID, then filtering by access level.
• How many times: Each item for the user is checked once against the filter condition.

How Execution Grows With Input

As the number of items for a user grows, the system checks each item's access level.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: The number of checks grows directly with the number of items to filter.

Final Time Complexity

Time Complexity: O(n)

This means the time to enforce fine-grained access grows linearly with the number of items checked.

Common Mistake

[X] Wrong: "Filtering by access level happens instantly regardless of item count."

[OK] Correct: Each item must be checked against the access rule, so more items mean more work.

Interview Connect

Understanding how access control scales helps you design systems that stay fast as data grows, a key skill in real projects.

Self-Check

"What if we added an index on AccessLevel to speed filtering? How would the time complexity change?"