Array-contains queries in Firebase - Time & Space Complexity

Time Complexity: Array-contains queries

O(n)

Understanding Time Complexity

When using array-contains queries in Firebase, it's important to know how the time to get results changes as your data grows.

We want to understand how the number of operations grows when searching for items inside arrays.

Scenario Under Consideration

Analyze the time complexity of the following operation sequence.

const query = firestore.collection('items')
  .where('tags', 'array-contains', 'blue');
const snapshot = await query.get();
const results = snapshot.docs.map(doc => doc.data());
    

This code searches the 'items' collection for documents where the 'tags' array includes the value 'blue'.

Identify Repeating Operations

• Primary operation: Querying the database to find documents with the matching array element.
• How many times: The query runs once, but internally it scans or uses an index over all documents with arrays containing the searched value.

How Execution Grows With Input

As the number of documents with arrays containing the searched value grows, the query must process more matches.

Input Size (n)	Approx. Api Calls/Operations
10	About 10 documents checked or returned
100	About 100 documents checked or returned
1000	About 1000 documents checked or returned

Pattern observation: The work grows roughly in direct proportion to the number of matching documents.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly with the number of documents that contain the searched array value.

Common Mistake

[X] Wrong: "The query time stays the same no matter how many documents match because it uses an index."

[OK] Correct: While indexes help find matches faster, the query still needs to process each matching document, so more matches mean more work.

Interview Connect

Understanding how queries scale helps you design better data models and explain your choices clearly in real projects or interviews.

Self-Check

"What if we changed 'array-contains' to 'array-contains-any' with multiple values? How would the time complexity change?"