Limit and pagination in DynamoDB - Time & Space Complexity

Time Complexity: Limit and pagination

O(n)

Understanding Time Complexity

When using limit and pagination in DynamoDB, we want to know how the time to get results changes as we ask for more data.

How does the number of items requested affect the work DynamoDB does?

Scenario Under Consideration

Analyze the time complexity of the following DynamoDB query with limit and pagination.

const params = {
  TableName: "Products",
  Limit: 10,
  ExclusiveStartKey: lastEvaluatedKey
};

const result = await dynamodb.query(params).promise();
const items = result.Items;
const lastEvaluatedKey = result.LastEvaluatedKey;

This code fetches up to 10 items from the "Products" table, starting after the last key from the previous page.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Reading items up to the limit from the table.
• How many times: Once per query call, fetching up to the limit number of items.

How Execution Grows With Input

As you ask for more items (increase the limit), DynamoDB reads more data.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with the number of items you ask for in each page.

Common Mistake

[X] Wrong: "Pagination makes queries always fast no matter how many items I want."

[OK] Correct: Each page still reads as many items as the limit, so asking for more items means more work and more time.

Interview Connect

Understanding how limit and pagination affect time helps you explain efficient data fetching in real projects.

Self-Check

"What if we remove the limit and try to fetch all items at once? How would the time complexity change?"