Pagination with SDK in DynamoDB - Time & Space Complexity

Time Complexity: Pagination with SDK

O(n)

Understanding Time Complexity

When using pagination with the DynamoDB SDK, we want to know how the time to get data changes as we ask for more pages.

We ask: How does the number of operations grow when we fetch more pages of results?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB SDK pagination code.

const params = { TableName: "MyTable", Limit: 10 };
let lastEvaluatedKey = null;
do {
  if (lastEvaluatedKey) {
    params.ExclusiveStartKey = lastEvaluatedKey;
  }
  const data = await dynamodbClient.scan(params).promise();
  lastEvaluatedKey = data.LastEvaluatedKey;
  processItems(data.Items);
} while (lastEvaluatedKey);
    

This code fetches items from a DynamoDB table in pages of 10, using the last key from the previous page to get the next.

Identify Repeating Operations

Look for repeated actions in the code.

• Primary operation: Calling the scan method to fetch a page of items.
• How many times: Once per page until no more pages remain.

How Execution Grows With Input

Each page fetch is a separate operation. More pages mean more calls.

Input Size (pages)	Approx. Operations (scan calls)
10	10
100	100
1000	1000

Pattern observation: The number of operations grows directly with the number of pages requested.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of pages you fetch.

Common Mistake

[X] Wrong: "Fetching more pages is just one operation because it's one loop."

[OK] Correct: Each page requires a separate network call and scan operation, so time adds up with each page.

Interview Connect

Understanding how pagination affects time helps you design efficient data fetching in real apps and shows you can think about performance clearly.

Self-Check

"What if we changed the Limit parameter to fetch 100 items per page instead of 10? How would the time complexity change?"