Device token management in Firebase - Time & Space Complexity

Time Complexity: Device token management

O(n)

Understanding Time Complexity

When managing device tokens in Firebase, it's important to know how the time to update or store tokens changes as more devices are involved.

We want to understand how the number of devices affects the work Firebase does.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const saveDeviceToken = async (userId, token) => {
  const userRef = firestore.collection('users').doc(userId);
  await userRef.update({
    deviceTokens: firebase.firestore.FieldValue.arrayUnion(token)
  });
};

// Called each time a device registers or refreshes its token

This code adds a new device token to a user's list of tokens in Firestore.

Identify Repeating Operations

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

• Primary operation: Firestore update call to add a token to the deviceTokens array.
• How many times: Once per device token registration or refresh.

How Execution Grows With Input

Each time a new device token is added, Firebase updates the user's document by adding the token to an array.

Input Size (n)	Approx. Api Calls/Operations
10	10 update calls, each adding one token
100	100 update calls, each adding one token
1000	1000 update calls, each adding one token

Pattern observation: The number of update calls grows directly with the number of device tokens added.

Final Time Complexity

Time Complexity: O(n)

This means the time to update device tokens grows linearly as the number of tokens increases.

Common Mistake

[X] Wrong: "Adding a token is always a single quick operation regardless of how many tokens exist."

[OK] Correct: Each update must check and modify the array, so as the array grows, the operation can take more time and resources.

Interview Connect

Understanding how operations scale with data size helps you design efficient cloud functions and database updates, a key skill in real projects.

Self-Check

"What if we stored device tokens in separate documents instead of an array? How would the time complexity change?"