Data denormalization strategies in Firebase - Time & Space Complexity

Time Complexity: Data denormalization strategies

O(n)

Understanding Time Complexity

When using data denormalization in Firebase, it is important to understand how the time to update or read data changes as the data grows.

We want to know how the number of operations changes when we duplicate data across multiple places.

Scenario Under Consideration

Analyze the time complexity of updating denormalized data in Firebase.

const updateUserName = async (userId, newName) => {
  // Update user name in main user record
  await db.ref(`users/${userId}/name`).set(newName);

  // Update user name in all posts by this user
  const postsSnapshot = await db.ref('posts').orderByChild('userId').equalTo(userId).once('value');
  postsSnapshot.forEach(post => {
    post.ref.child('userName').set(newName);
  });
};

This code updates a user's name in their main profile and then updates all posts they made with the new name.

Identify Repeating Operations

Look at what repeats when updating denormalized data.

• Primary operation: Writing the new name to each post made by the user.
• How many times: Once for the main user record, then once for each post by that user.

How Execution Grows With Input

As the number of posts by a user grows, the number of update operations grows too.

Input Size (number of posts)	Approx. Api Calls/Operations
10	11 (1 user update + 10 post updates)
100	101 (1 user update + 100 post updates)
1000	1001 (1 user update + 1000 post updates)

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

Final Time Complexity

Time Complexity: O(n)

This means the time to update grows linearly with the number of denormalized entries to update.

Common Mistake

[X] Wrong: "Updating the main user record automatically updates all denormalized copies instantly."

[OK] Correct: Each denormalized copy must be updated separately, so the time grows with how many copies exist.

Interview Connect

Understanding how denormalization affects update time helps you design scalable Firebase apps and shows you can think about real-world data costs.

Self-Check

What if we stored user names only in the main user record and referenced them in posts without copying? How would the time complexity change?