Single-table design methodology in DynamoDB - Time & Space Complexity

Time Complexity: Single-table design methodology

O(n)

Understanding Time Complexity

When using single-table design in DynamoDB, it's important to understand how the number of operations changes as your data grows.

We want to know how the time to get or write data changes when the table gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query using single-table design.

    const params = {
      TableName: "MySingleTable",
      KeyConditionExpression: "PK = :pkValue",
      ExpressionAttributeValues: {
        ":pkValue": "USER#123"
      }
    };
    const result = await dynamodb.query(params).promise();
    

This code queries all items with a partition key of "USER#123" from a single table that stores many entity types together.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Querying items by partition key.
• How many times: The query reads all items matching the partition key, which depends on how many related items the user has.

How Execution Grows With Input

As the number of items for a user grows, the query reads more data.

Input Size (n)	Approx. Operations
10	Reads 10 items
100	Reads 100 items
1000	Reads 1000 items

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

Final Time Complexity

Time Complexity: O(n)

This means the time to get all items grows linearly with how many items share the same partition key.

Common Mistake

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

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

Interview Connect

Understanding how single-table design affects query time helps you explain your choices clearly and shows you know how data size impacts performance.

Self-Check

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