Tables, items, and attributes in AWS - Time & Space Complexity

Time Complexity: Tables, items, and attributes

O(n)

Understanding Time Complexity

When working with tables, items, and attributes in AWS databases, it is important to understand how the time to perform operations changes as the data grows.

We want to know how the number of operations or API calls changes when we add more items or attributes.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

// Create a table
aws dynamodb create-table --table-name MyTable --attribute-definitions AttributeName=Id,AttributeType=S --key-schema AttributeName=Id,KeyType=HASH --provisioned-throughput ReadCapacityUnits=5,WriteCapacityUnits=5

// Put multiple items
for i in range(1, n+1):
  aws dynamodb put-item --table-name MyTable --item '{"Id": {"S": "item" + str(i)}, "Value": {"S": "data"}}'

// Get an item by key
aws dynamodb get-item --table-name MyTable --key '{"Id": {"S": "item42"}}'

This sequence creates a table, adds multiple items, and retrieves one item by its key.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Putting items into the table (put-item API call)
• How many times: Once per item, so n times for n items
• Getting an item by key happens once, so less impact on growth

How Execution Grows With Input

As the number of items (n) increases, the number of put-item calls grows directly with n.

Input Size (n)	Approx. Api Calls/Operations
10	10 put-item calls + 1 get-item call = 11
100	100 put-item calls + 1 get-item call = 101
1000	1000 put-item calls + 1 get-item call = 1001

Pattern observation: The total operations grow roughly in a straight line with the number of items added.

Final Time Complexity

Time Complexity: O(n)

This means the time or number of operations grows directly in proportion to the number of items you add.

Common Mistake

[X] Wrong: "Getting an item by key takes longer as the table grows because it searches all items."

[OK] Correct: DynamoDB uses keys to find items quickly, so getting an item by key takes about the same time no matter how many items are in the table.

Interview Connect

Understanding how operations grow with data size helps you design efficient cloud databases and answer questions confidently in interviews.

Self-Check

"What if we changed from putting items one by one to batch writing multiple items at once? How would the time complexity change?"