Time Complexity: Identifying missing indexes
O(n)
0
0
Identifying missing indexes in MongoDB - Time & Space Complexity
Understanding Time Complexity
When we look for missing indexes in MongoDB, we want to understand how the time to find data grows as the data grows.
We ask: How does the search time change if we don't have the right index?
Scenario Under Consideration
Analyze the time complexity of the following MongoDB query without an index.
db.orders.find({ customerId: 12345 })
This query searches for all orders from a specific customer in the orders collection.
Identify Repeating Operations
Look at what repeats when the query runs without an index.
- Primary operation: Scanning each document in the collection one by one.
- How many times: Once for every document in the collection.
How Execution Grows With Input
As the number of documents grows, the time to find matching orders grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 document checks |
| 100 | 100 document checks |
| 1000 | 1000 document checks |
Pattern observation: The number of checks grows directly with the number of documents.
Final Time Complexity
Time Complexity: O(n)
This means the search time grows linearly with the number of documents when no index is used.
Common Mistake
[X] Wrong: "The database will find the data instantly even without indexes."
[OK] Correct: Without indexes, the database must look at every document, so it takes longer as data grows.
Interview Connect
Understanding how missing indexes affect query time helps you explain why indexes matter in real projects.
Self-Check
"What if we add an index on customerId? How would the time complexity change?"