Time Complexity: Query patterns that cause collection scans
O(n)
0
0
Query patterns that cause collection scans in MongoDB - Time & Space Complexity
Understanding Time Complexity
When MongoDB runs a query without using an index, it looks at every document in the collection. This is called a collection scan.
We want to understand how the time to run such queries grows as the collection gets bigger.
Scenario Under Consideration
Analyze the time complexity of the following MongoDB query.
db.products.find({ price: { $gt: 100 } })
This query finds all products with a price greater than 100. Assume there is no index on the price field.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- 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 query looks at each document once.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 document checks |
| 100 | 100 document checks |
| 1000 | 1000 document checks |
Pattern observation: The work grows directly with the number of documents. Double the documents, double the work.
Final Time Complexity
Time Complexity: O(n)
This means the query time grows in a straight line as the collection size grows.
Common Mistake
[X] Wrong: "MongoDB always uses indexes, so query time stays the same no matter how big the collection is."
[OK] Correct: If there is no index on the queried field, MongoDB must check every document, so query time grows with collection size.
Interview Connect
Understanding when queries cause collection scans helps you explain performance issues clearly and shows you know how databases work under the hood.
Self-Check
"What if we added an index on the price field? How would the time complexity change?"