Distributed counters pattern in Firebase - Time & Space Complexity

Time Complexity: Distributed counters pattern

O(n)

Understanding Time Complexity

When using distributed counters in Firebase, it's important to understand how the number of operations grows as the counter updates increase.

We want to know how the work changes when many increments happen across multiple shards.

Scenario Under Consideration

Analyze the time complexity of the following Firebase distributed counter update.

const shardId = Math.floor(Math.random() * numShards);
const shardRef = db.collection('counters').doc(counterId).collection('shards').doc(shardId.toString());
await shardRef.update({ count: firebase.firestore.FieldValue.increment(1) });
    

This code increments one shard's count randomly to spread load and avoid contention.

Identify Repeating Operations

Look at what repeats when many increments happen.

• Primary operation: One update call to a single shard document per increment.
• How many times: Once per increment, distributed randomly across shards.

How Execution Grows With Input

Each increment triggers exactly one update to one shard document.

Input Size (n)	Approx. API Calls/Operations
10	10 update calls
100	100 update calls
1000	1000 update calls

Pattern observation: The number of update calls grows directly with the number of increments.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows linearly with the number of increments made.

Common Mistake

[X] Wrong: "Updating one shard means the total work stays constant no matter how many increments happen."

[OK] Correct: Each increment still requires one update call, so total work grows with increments, not stays fixed.

Interview Connect

Understanding how distributed counters scale helps you design systems that handle many users updating data without slowing down.

Self-Check

"What if we increased the number of shards? How would that affect the time complexity of increments?"