Fan-out writes pattern in Firebase - Time & Space Complexity

Time Complexity: Fan-out writes pattern

O(n)

Understanding Time Complexity

When using the fan-out writes pattern in Firebase, we write the same data to many places at once.

We want to know how the time it takes grows as we write to more locations.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const updates = {};
const data = { name: "Alice", age: 30 };
const userId = "user123";
const postId = "post456";

updates[`/users/${userId}`] = data;
updates[`/posts/${postId}/author`] = data;
updates[`/feeds/${userId}/${postId}`] = data;

firebase.database().ref().update(updates);
    

This code writes the same data to multiple paths in the database at once using a fan-out update.

Identify Repeating Operations

Identify the API calls, resource provisioning, data transfers that repeat.

• Primary operation: Writing data to multiple database paths in one update call.
• How many times: The number of paths we write to (3 in this example, but can be many more).

How Execution Grows With Input

Each additional path we write to adds one more piece of data to send in the update.

Input Size (n)	Approx. API Calls/Operations
10	1 update call with 10 paths
100	1 update call with 100 paths
1000	1 update call with 1000 paths

Pattern observation: The number of paths grows, but all are sent in a single update call, so the operation count stays one, but the data size grows linearly.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the write grows in direct proportion to the number of paths we update.

Common Mistake

[X] Wrong: "Because we use one update call, the time stays the same no matter how many paths we write to."

[OK] Correct: Even though it's one call, the data size grows with each path, so the time to send and process the data grows too.

Interview Connect

Understanding how fan-out writes scale helps you design efficient database updates and shows you can think about how cloud operations grow with data size.

Self-Check

"What if we split the fan-out writes into multiple smaller update calls instead of one big update? How would the time complexity change?"