Denormalization trade-offs in MongoDB - Time & Space Complexity

Time Complexity: Denormalization trade-offs

O(n)

Understanding Time Complexity

When we denormalize data in MongoDB, we copy related information into one place to speed up reads.

We want to understand how this affects the time it takes to update or read data as the data grows.

Scenario Under Consideration

Analyze the time complexity of updating a denormalized document.

// Update user info in many posts where user data is embedded
const userId = "123";
const newName = "Alice";
db.posts.updateMany(
  { "author.id": userId },
  { $set: { "author.name": newName } }
);
    

This code updates all posts where the author's id matches, changing the embedded author name.

Identify Repeating Operations

Look for repeated work done by the database.

• Primary operation: Scanning and updating each post with matching author id.
• How many times: Once for each post by that author, which can be many.

How Execution Grows With Input

As the number of posts by the user grows, the updates take longer.

Input Size (n posts)	Approx. Operations
10	10 updates
100	100 updates
1000	1000 updates

Pattern observation: The work grows directly with the number of posts to update.

Final Time Complexity

Time Complexity: O(n)

This means the update time grows linearly with how many documents need changing.

Common Mistake

[X] Wrong: "Denormalization always makes updates faster because data is in one place."

[OK] Correct: Actually, denormalization can slow updates because you must change many copies of the same data.

Interview Connect

Understanding these trade-offs shows you can think about real-world data design and performance, a key skill in database work.

Self-Check

"What if we used references instead of embedding author data? How would the time complexity of updates change?"