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?"

Practice

1. What is the main purpose of a table in AWS DynamoDB?

easy

A. To store items, which are records

B. To run code functions

C. To manage user permissions

D. To host websites

Solution

1. Step 1: Understand the role of a table in DynamoDB

   A table is a container that holds items, which are like rows in a database.

2. Step 2: Identify the correct purpose

   Since tables store items (records), this matches To store items, which are records.

3. Final Answer:

   To store items, which are records -> Option A

4. Quick Check:

   Table = container for items [OK]

Hint: Tables hold records called items [OK]

Common Mistakes:

• Confusing tables with code functions
• Thinking tables manage permissions
• Assuming tables host websites

2. Which of the following is the correct way to define an item attribute in DynamoDB?

easy

A. ("Name", "John", "Age", 30)

B. {"Name": "John", "Age": 30}

C. ["Name", "John", "Age", 30]

D. "Name": "John", "Age": 30

Solution

1. Step 1: Recognize the attribute format

   Attributes are key-value pairs, best represented as JSON objects with keys and values.

2. Step 2: Match the correct syntax

   {"Name": "John", "Age": 30} shows a JSON object with keys "Name" and "Age" and their values, which is correct.

3. Final Answer:

   {"Name": "John", "Age": 30} -> Option B

4. Quick Check:

   Attributes = key-value pairs in JSON [OK]

Hint: Attributes are key-value pairs in JSON format [OK]

Common Mistakes:

• Using arrays instead of key-value pairs
• Using tuples instead of objects
• Omitting braces for JSON objects

3. Given a DynamoDB table with primary key "UserID", what happens if you try to add two items with the same UserID but different attributes?

medium

A. Both items are stored separately

B. The table creates a duplicate primary key

C. An error is thrown and no item is added

D. The second item overwrites the first item

Solution

1. Step 1: Understand primary key uniqueness

   In DynamoDB, the primary key must be unique for each item in the table.

2. Step 2: Effect of duplicate primary key

   If you add an item with an existing primary key, it replaces the old item with the new one.

3. Final Answer:

   The second item overwrites the first item -> Option D

4. Quick Check:

   Duplicate key = overwrite existing item [OK]

Hint: Duplicate primary keys overwrite existing items [OK]

Common Mistakes:

• Thinking both items are stored separately
• Expecting an error on duplicate keys
• Assuming duplicates are allowed

4. You try to insert an item into a DynamoDB table but get an error. The item has no primary key attribute. What is the most likely cause?

medium

A. Missing required primary key attribute in the item

B. Table is full and cannot accept new items

C. Attributes have invalid data types

D. You exceeded the maximum number of attributes

Solution

1. Step 1: Recall primary key requirement

   Every item must have the primary key attribute to be uniquely identified in the table.

2. Step 2: Identify cause of error

   If the item lacks the primary key attribute, DynamoDB rejects it with an error.

3. Final Answer:

   Missing required primary key attribute in the item -> Option A

4. Quick Check:

   Primary key missing causes insert error [OK]

Hint: Every item must include the primary key attribute [OK]

Common Mistakes:

• Assuming table capacity causes insert errors
• Blaming attribute data types without checking keys
• Thinking attribute count limits cause this error

5. You want to design a DynamoDB table to store user profiles. Each user has a unique UserID and may have multiple email addresses. How should you structure the table and items to handle this?

hard

A. Use email as the primary key and ignore UserID

B. Use UserID as the primary key and create a separate item for each email

C. Use UserID as the primary key and store emails as a list attribute inside each item

D. Create multiple tables, one per email address

Solution

1. Step 1: Identify unique identifier

   UserID uniquely identifies each user, so it should be the primary key.

2. Step 2: Store multiple emails

   Since a user can have multiple emails, store them as a list attribute inside the user item.

3. Step 3: Evaluate other options

   Creating separate items per email duplicates UserID or loses uniqueness; using email as key ignores UserID; multiple tables is inefficient.

4. Final Answer:

   Use UserID as the primary key and store emails as a list attribute inside each item -> Option C

5. Quick Check:

   Primary key + list attribute for multiple values [OK]

Hint: Use primary key for user, list attribute for multiple emails [OK]

Common Mistakes:

• Using email as primary key instead of UserID
• Creating multiple items for one user
• Making multiple tables unnecessarily