Many-to-many with GSI overloading in DynamoDB - Time & Space Complexity

Time Complexity: Many-to-many with GSI overloading

O(n)

Understanding Time Complexity

When using many-to-many relationships with GSI overloading in DynamoDB, it is important to understand how the number of operations grows as data increases.

We want to know how query time changes when more related items exist.

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query using a GSI to find related items.

// Query items related to a given key using GSI
const params = {
  TableName: 'RelationsTable',
  IndexName: 'GSI1',
  KeyConditionExpression: 'GSI1PK = :key',
  ExpressionAttributeValues: { ':key': 'USER#123' }
};
const result = await dynamodb.query(params).promise();

This code queries the GSI to find all items related to USER#123 in a many-to-many setup.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Querying all items matching the GSI partition key.
• How many times: Once per query, but the number of matching items can vary.

How Execution Grows With Input

As the number of related items grows, the query must process more data.

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

Pattern observation: The work grows roughly in direct proportion to the number of related items.

Final Time Complexity

Time Complexity: O(n)

This means the query time increases linearly with the number of related items found.

Common Mistake

[X] Wrong: "Querying a GSI always takes constant time regardless of data size."

[OK] Correct: The query time depends on how many items match the GSI key, so more related items mean more work.

Interview Connect

Understanding how queries scale with data size in many-to-many relationships shows you can design efficient data access patterns in DynamoDB.

Self-Check

"What if we added pagination to limit results per query? How would that affect the time complexity?"