Time Complexity: limit method for pagination
O(n)
0
0
limit method for pagination in MongoDB - Time & Space Complexity
Understanding Time Complexity
When using the limit method for pagination in MongoDB, it's important to understand how the time to get results changes as we ask for more data.
We want to know how the number of operations grows when we increase the limit value.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
// Fetch first 10 documents from a collection
db.collection.find().limit(10)
// Fetch next 10 documents skipping the first 10
// for pagination
// db.collection.find().skip(10).limit(10)
This code fetches a limited number of documents from the database, often used to show pages of results.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Scanning documents to collect the limited number requested.
- How many times: The database reads documents until it reaches the limit number.
How Execution Grows With Input
As the limit number grows, the database reads more documents to return the results.
| Input Size (limit) | Approx. Operations |
|---|---|
| 10 | Reads about 10 documents |
| 100 | Reads about 100 documents |
| 1000 | Reads about 1000 documents |
Pattern observation: The work grows roughly in direct proportion to the limit size.
Final Time Complexity
Time Complexity: O(n)
This means if you ask for twice as many documents, the database roughly does twice as much work.
Common Mistake
[X] Wrong: "Using limit means the database only does a fixed small amount of work no matter the limit."
[OK] Correct: The database must read as many documents as the limit to return them, so work grows with the limit size.
Interview Connect
Understanding how limit affects performance helps you explain how pagination works efficiently in real apps.
Self-Check
What if we add a skip before limit for pagination? How would the time complexity change?