Query result ordering (ascending, descending) in DynamoDB - Time & Space Complexity

Time Complexity: Query result ordering (ascending, descending)

O(n)

Understanding Time Complexity

When we ask DynamoDB to return items in order, we want to know how the time it takes changes as we get more data.

We are trying to see how sorting results affects the work DynamoDB does.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Query items from a DynamoDB table
const params = {
  TableName: "Orders",
  KeyConditionExpression: "CustomerId = :cid",
  ExpressionAttributeValues: {
    ":cid": { S: "12345" }
  },
  ScanIndexForward: false // false means descending order
};
const result = await dynamodb.query(params).promise();
    

This code fetches all orders for a customer and returns them in descending order by sort key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DynamoDB reads each matching item once to return it.
• How many times: Once per matching item in the query result.

How Execution Grows With Input

As the number of matching items grows, DynamoDB reads more items to return them in order.

Input Size (n)	Approx. Operations
10	About 10 reads
100	About 100 reads
1000	About 1000 reads

Pattern observation: The work grows directly with the number of items returned, whether ascending or descending.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with how many items match the query, regardless of order direction.

Common Mistake

[X] Wrong: "Ordering results descending makes the query slower than ascending."

[OK] Correct: DynamoDB stores data sorted by the sort key, so reading in ascending or descending order just changes the direction of reading, not the amount of work.

Interview Connect

Understanding how DynamoDB handles ordering helps you explain how queries scale and shows you know how databases manage data efficiently.

Self-Check

"What if we added a filter expression after the query? How would that affect the time complexity?"