Optimistic concurrency in Firebase - Time & Space Complexity

Time Complexity: Optimistic concurrency

O(n)

Understanding Time Complexity

When using optimistic concurrency in Firebase, we want to know how the number of operations changes as more users try to update data at the same time.

We ask: How does the system handle conflicts and how many retries might happen?

Scenario Under Consideration

Analyze the time complexity of this optimistic concurrency update:

const docRef = firestore.collection('items').doc('item1');

firestore.runTransaction(async (transaction) => {
  const doc = await transaction.get(docRef);
  const currentCount = doc.data().count || 0;
  transaction.update(docRef, { count: currentCount + 1 });
  return Promise.resolve();
});

This code tries to read a document, increment a count, and write it back safely using a transaction that retries if conflicts happen.

Identify Repeating Operations

Look at what repeats when many users update the same document:

• Primary operation: Reading and writing the document inside a transaction.
• How many times: The transaction may retry multiple times if others update the document simultaneously.

How Execution Grows With Input

As more users try to update at once, retries increase because transactions conflict.

Input Size (n)	Approx. Api Calls/Operations
10	About 10-15 calls (some retries)
100	More than 100 calls (many retries)
1000	Much more than 1000 calls (high retry rate)

Pattern observation: The number of retries grows as more users try to update simultaneously, increasing total operations.

Final Time Complexity

Time Complexity: O(n)

This means the total operations grow roughly in proportion to the number of concurrent updates trying to happen.

Common Mistake

[X] Wrong: "The transaction will only run once no matter how many users update at the same time."

[OK] Correct: When many users update simultaneously, transactions can conflict and retry multiple times, increasing operations.

Interview Connect

Understanding how optimistic concurrency scales helps you design systems that handle many users safely and efficiently.

Self-Check

What if we changed from optimistic concurrency to a simple write without transactions? How would the time complexity and conflict handling change?