Adjacency list pattern in DynamoDB - Time & Space Complexity

Time Complexity: Adjacency list pattern

O(n)

Understanding Time Complexity

When working with the adjacency list pattern in DynamoDB, it's important to understand how the time to get connected items grows as the list grows.

We want to know how the number of operations changes when we fetch related nodes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Fetch all child nodes for a given parent node
const params = {
  TableName: "GraphTable",
  KeyConditionExpression: "ParentId = :pid",
  ExpressionAttributeValues: {
    ":pid": { S: "parent123" }
  }
};
const result = await dynamodb.query(params).promise();
return result.Items;
    

This code fetches all child nodes linked to a specific parent node using the adjacency list pattern.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Querying DynamoDB to get all children of one parent.
• How many times: Once per parent node, but returns multiple child items.

How Execution Grows With Input

As the number of children for a parent grows, the query returns more items, so the work grows with the number of children.

Input Size (n = number of children)	Approx. Operations
10	About 10 items fetched
100	About 100 items fetched
1000	About 1000 items fetched

Pattern observation: The time grows roughly in direct proportion to the number of children returned.

Final Time Complexity

Time Complexity: O(n)

This means the time to get all children grows linearly with how many children there are.

Common Mistake

[X] Wrong: "Querying a parent node always takes constant time regardless of children count."

[OK] Correct: The query returns all children, so if there are many children, it takes longer to fetch and process them all.

Interview Connect

Understanding how data retrieval time grows with connected items helps you design efficient queries and explain your choices clearly in interviews.

Self-Check

"What if we added pagination to limit the number of children returned per query? How would the time complexity change?"