Cost estimation for access patterns in DynamoDB - Time & Space Complexity

Time Complexity: Cost estimation for access patterns

O(n)

Understanding Time Complexity

When using DynamoDB, it is important to understand how the cost of accessing data grows as your data or requests increase.

We want to know how the number of operations changes when we use different ways to get data.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB access pattern.

// Query items by partition key
const params = {
  TableName: "Orders",
  KeyConditionExpression: "CustomerId = :cid",
  ExpressionAttributeValues: {
    ":cid": { S: "12345" }
  }
};
const result = await dynamodb.query(params).promise();
    

This code fetches all orders for one customer using their ID as the partition key.

Identify Repeating Operations

Look for repeated actions that affect cost.

• Primary operation: Reading items matching the partition key.
• How many times: Once per item returned in the query result.

How Execution Grows With Input

As the number of orders for a customer grows, the work to fetch them grows too.

Input Size (n)	Approx. Operations
10	10 reads
100	100 reads
1000	1000 reads

Pattern observation: The number of reads grows directly with the number of items returned.

Final Time Complexity

Time Complexity: O(n)

This means the time to get data grows in a straight line with the number of matching items.

Common Mistake

[X] Wrong: "Querying by partition key always takes the same time no matter how many items match."

[OK] Correct: The query reads each matching item, so more items mean more work and time.

Interview Connect

Understanding how data access cost grows helps you design better queries and explain your choices clearly in real projects.

Self-Check

"What if we changed the query to use a filter after fetching all partition keys? How would the time complexity change?"