NoSQL vs relational database comparison in DynamoDB - Performance Comparison

Time Complexity: NoSQL vs relational database comparison

O(1)

Understanding Time Complexity

When comparing NoSQL and relational databases, it's important to understand how their operations scale as data grows.

We want to see how the time to access or modify data changes when the amount of data increases.

Scenario Under Consideration

Analyze the time complexity of a simple data retrieval in DynamoDB (NoSQL) versus a relational database query.

// DynamoDB GetItem example
const params = {
  TableName: "Users",
  Key: { "UserID": "123" }
};
const result = await dynamodb.getItem(params).promise();

-- Relational SQL example
SELECT * FROM Users WHERE UserID = '123';
    

This code fetches a single user record by its unique ID in both database types.

Identify Repeating Operations

Look at what operations repeat or take time as data grows.

• Primary operation: Searching for a record by key.
• How many times: One direct lookup per query, no loops in this example.

How Execution Grows With Input

As the number of records grows, how does the time to find one record change?

Input Size (n)	Approx. Operations
10	1 lookup
100	1 lookup
1000	1 lookup

Pattern observation: The time stays about the same because both use indexes to find the record directly.

Final Time Complexity

Time Complexity: O(1)

This means the time to get a record by its key stays constant no matter how much data there is.

Common Mistake

[X] Wrong: "NoSQL databases are always faster than relational databases because they don't use joins."

[OK] Correct: The speed depends on the operation and indexing, not just the database type. Both can do fast key lookups.

Interview Connect

Understanding how data retrieval scales helps you explain database choices clearly and confidently in real-world situations.

Self-Check

"What if we changed the query to search by a non-key attribute without an index? How would the time complexity change?"