Time Complexity: In and not-in queries
O(n)
0
0
In and not-in queries in Firebase - Time & Space Complexity
Understanding Time Complexity
When using Firebase queries with "in" or "not-in" filters, it's important to know how the number of items you check affects the work done.
We want to understand how the query cost grows as we add more values to these filters.
Scenario Under Consideration
Analyze the time complexity of the following operation sequence.
const query = firestore.collection('products')
.where('category', 'in', ['electronics', 'books', 'clothing']);
const snapshot = await query.get();
This code fetches all products whose category is one of the listed values using an "in" query.
Identify Repeating Operations
Identify the API calls, resource provisioning, data transfers that repeat.
- Primary operation: One query to Firestore with an "in" filter containing multiple values.
- How many times: The query internally performs multiple lookups, one for each value in the "in" list.
How Execution Grows With Input
Each additional value in the "in" list causes Firestore to perform an extra lookup to find matching documents.
| Input Size (n) | Approx. API Calls/Operations |
|---|---|
| 3 | 3 lookups (one per category value) |
| 5 | 5 lookups |
| 10 | 10 lookups |
Pattern observation: The number of internal lookups grows directly with the number of values in the "in" list.
Final Time Complexity
Time Complexity: O(n)
This means the work done grows linearly with the number of values you include in the "in" or "not-in" query.
Common Mistake
[X] Wrong: "Adding more values to the 'in' list does not affect query cost because it's a single query call."
[OK] Correct: Even though it looks like one query, Firestore performs separate lookups internally for each value, so cost grows with the list size.
Interview Connect
Understanding how query filters affect performance helps you design efficient data fetching in real projects and shows you think about cost and speed.
Self-Check
"What if we replaced the 'in' query with multiple separate queries, one per value? How would the time complexity change?"