Time Complexity: Many-to-many with references
O(n)
0
0
Many-to-many with references in MongoDB - Time & Space Complexity
Understanding Time Complexity
When working with many-to-many relationships in MongoDB using references, it's important to understand how the time to get data grows as the number of linked items grows.
We want to know how the number of operations changes when fetching related data from multiple collections.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
// Find all students and their courses
const students = db.students.find().toArray();
for (const student of students) {
const courses = db.courses.find({ _id: { $in: student.courseIds } }).toArray();
// process student with courses
}
This code fetches all students, then for each student fetches all courses they are linked to by IDs.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Looping over each student and querying courses for each.
- How many times: Once per student, and inside that, a query for their courses.
How Execution Grows With Input
As the number of students grows, the number of course queries grows too, since each student triggers a separate query.
| Input Size (n students) | Approx. Operations |
|---|---|
| 10 | 1 student query + 10 course queries |
| 100 | 1 student query + 100 course queries |
| 1000 | 1 student query + 1000 course queries |
Pattern observation: The total operations grow roughly in direct proportion to the number of students.
Final Time Complexity
Time Complexity: O(n)
This means the time to fetch all students and their courses grows linearly with the number of students.
Common Mistake
[X] Wrong: "Fetching courses for all students is just one query, so it's constant time regardless of students."
[OK] Correct: Each student's courses are fetched separately, so the number of queries grows with students, making the total time grow too.
Interview Connect
Understanding how many queries run and how they grow with data size is a key skill. It helps you design better data fetching strategies and explain your choices clearly.
Self-Check
"What if we changed the code to fetch all courses for all students in a single query instead of one per student? How would the time complexity change?"