Key condition expressions in DynamoDB - Time & Space Complexity

Time Complexity: Key condition expressions

O(n)

Understanding Time Complexity

When using key condition expressions in DynamoDB, we want to know how the time to get data changes as the amount of data grows.

We ask: How does the query time grow when we have more items in the table or partition?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query using a key condition expression.

const params = {
  TableName: "Music",
  KeyConditionExpression: "Artist = :artistName",
  ExpressionAttributeValues: {
    ":artistName": "No One You Know"
  }
};
const result = await dynamodb.query(params).promise();
    

This code queries the "Music" table for all items where the Artist equals "No One You Know" using a key condition expression.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Scanning items in the partition matching the key condition.
• How many times: Once per matching item in the partition.

How Execution Grows With Input

As the number of items with the same key grows, the query checks each matching item.

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

Pattern observation: The time grows roughly in direct proportion to the number of matching items.

Final Time Complexity

Time Complexity: O(n)

This means the query time grows linearly with the number of items that match the key condition.

Common Mistake

[X] Wrong: "The query always takes the same time no matter how many items match."

[OK] Correct: The query must read each matching item, so more matches mean more work and longer time.

Interview Connect

Understanding how query time grows with data size helps you explain efficient data access in DynamoDB, a key skill for working with real databases.

Self-Check

"What if we added a sort key condition to narrow results? How would the time complexity change?"