Why document databases over relational in MongoDB - Performance Analysis

Time Complexity: Why document databases over relational

O(1)

Understanding Time Complexity

We want to understand how the time it takes to work with data changes when using document databases compared to relational databases.

Specifically, we ask: How does the structure of data affect the speed of common operations?

Scenario Under Consideration

Analyze the time complexity of a simple MongoDB query that finds a document by its ID and updates a nested field.

// Find a user by ID and update their address city
const userId = ObjectId("12345");
db.users.updateOne(
  { _id: userId },
  { $set: { "address.city": "New City" } }
);
    

This code finds one user document by its unique ID and updates the city inside the nested address field.

Identify Repeating Operations

Look for repeated steps or loops in the operation.

• Primary operation: Searching for a document by its unique ID.
• How many times: This happens once per query, no loops over multiple documents.

How Execution Grows With Input

As the number of documents grows, finding by ID stays fast because of indexing.

Input Size (n)	Approx. Operations
10	Few operations, quick find
100	Still very few operations, quick find
1000	Still very few operations, quick find

Pattern observation: The time to find by ID does not grow much as data grows because indexes help keep it fast.

Final Time Complexity

Time Complexity: O(1)

This means the time to find and update a document by ID stays about the same no matter how many documents there are.

Common Mistake

[X] Wrong: "Finding a document by ID gets slower as the database grows because it has to check every document."

[OK] Correct: Document databases use indexes on IDs, so they jump directly to the right document without checking all others.

Interview Connect

Understanding how document databases handle queries efficiently shows you know how data structure and indexing affect speed. This skill helps you explain why certain databases fit some jobs better than others.

Self-Check

"What if we searched for a document by a field without an index? How would the time complexity change?"