Time Complexity: One-to-many referencing pattern
O(n)
0
0
One-to-many referencing pattern in MongoDB - Time & Space Complexity
Understanding Time Complexity
When using one-to-many referencing in MongoDB, we want to know how the time to get data changes as the number of related items grows.
We ask: How does fetching a document and its related many documents scale with more data?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
// Find a user by ID
const user = db.users.findOne({ _id: userId });
// Find all posts referencing this user
const posts = db.posts.find({ userId: user._id }).toArray();
This code fetches one user and then fetches all posts linked to that user by userId.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Scanning all posts that match the userId.
- How many times: Once for the user, then once for each post linked to that user.
How Execution Grows With Input
As the number of posts for a user grows, the time to fetch all posts grows roughly the same way.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 posts | About 10 operations to fetch posts |
| 100 posts | About 100 operations to fetch posts |
| 1000 posts | About 1000 operations to fetch posts |
Pattern observation: The time grows directly with the number of posts linked to the user.
Final Time Complexity
Time Complexity: O(n)
This means the time to get all related posts grows linearly with how many posts there are for that user.
Common Mistake
[X] Wrong: "Fetching related posts is always fast no matter how many posts exist."
[OK] Correct: The more posts linked to a user, the longer it takes to fetch them all, so time grows with data size.
Interview Connect
Understanding how fetching related data scales helps you explain database design choices clearly and shows you think about real data growth.
Self-Check
"What if we stored all posts inside the user document instead of referencing? How would the time complexity change when fetching posts?"