Time Complexity: How MongoDB scans documents
O(n)
0
0
How MongoDB scans documents - Performance & Efficiency
Understanding Time Complexity
When MongoDB looks for data, it scans documents to find matches. Understanding how long this takes helps us know how fast queries run.
We want to see how the time to scan grows as the number of documents grows.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
// Find all documents where age is 25
db.users.find({ age: 25 })
This query scans the users collection to find documents with age equal to 25.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Scanning each document in the collection to check the age field.
- How many times: Once for every document in the collection.
How Execution Grows With Input
As the number of documents grows, MongoDB checks more documents one by one.
| 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 time to find matching documents grows in a straight line as the collection gets bigger.
Common Mistake
[X] Wrong: "MongoDB instantly finds matching documents no matter the collection size."
[OK] Correct: Without indexes, MongoDB must look at each document one by one, so bigger collections take more time.
Interview Connect
Knowing how MongoDB scans documents helps you explain query speed and shows you understand how databases work behind the scenes.
Self-Check
"What if we added an index on the age field? How would the time complexity change?"