Basic scan operation in DynamoDB - Time & Space Complexity

Time Complexity: Basic scan operation

O(n)

Understanding Time Complexity

When we use a scan operation in DynamoDB, it looks through all the items in a table. Understanding how long this takes helps us know how it will behave as the table grows.

We want to find out how the time needed changes when the number of items increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

const params = {
  TableName: "MyTable"
};

const data = await dynamodb.scan(params).promise();
console.log(data.Items);
    

This code scans the entire "MyTable" and returns all items found.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading each item in the table one by one.
• How many times: Once for every item in the table.

How Execution Grows With Input

As the number of items grows, the scan must look at each item, so the work grows steadily.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to scan grows in a straight line with the number of items in the table.

Common Mistake

[X] Wrong: "Scan only reads a few items, so it's always fast."

[OK] Correct: Scan reads every item in the table, so if the table is big, it takes longer.

Interview Connect

Knowing how scan time grows helps you explain why it's better to use queries or indexes when possible. This shows you understand how database operations scale.

Self-Check

"What if we added a filter expression to the scan? How would the time complexity change?"