Embedded documents (nested objects) in MongoDB - Time & Space Complexity

Time Complexity: Embedded documents (nested objects)

O(n * m)

Understanding Time Complexity

When working with embedded documents in MongoDB, it is important to understand how the time to access or query data changes as the size of the nested objects grows.

We want to know how the number of operations grows when we look inside these nested objects.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find all users with a specific hobby inside embedded documents
db.users.find({ "profile.hobbies.name": "reading" })

This query searches inside the embedded "profile" document for a hobby named "reading".

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each user document and then scanning the embedded hobbies array inside the profile.
• How many times: For each user, the query checks each hobby in the embedded array until it finds a match or finishes the list.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 users, 5 hobbies each	~50 checks
100 users, 5 hobbies each	~500 checks
100 users, 50 hobbies each	~5,000 checks

Pattern observation: The total checks grow with the number of users times the number of hobbies per user.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows with the number of documents (n) times the number of embedded items (m) inside each document.

Common Mistake

[X] Wrong: "Querying embedded documents is always fast because data is nested inside one document."

[OK] Correct: If the embedded array is large, the query must check many items inside each document, which can take more time as the array grows.

Interview Connect

Understanding how nested data affects query time helps you explain real-world database performance and design better data models.

Self-Check

"What if we added an index on the embedded field 'profile.hobbies.name'? How would the time complexity change?"

Practice

1. What is an embedded document in MongoDB?

easy

A. A document stored inside another document as a nested object

B. A separate collection linked by an ID

C. A document stored in a different database

D. A document stored as a file on disk

Solution

1. Step 1: Understand MongoDB document structure

   MongoDB stores data in documents, which can contain nested objects called embedded documents.

2. Step 2: Identify embedded document meaning

   An embedded document is a document inside another document, not a separate collection or file.

3. Final Answer:

   A document stored inside another document as a nested object -> Option A

4. Quick Check:

   Embedded document = nested object inside document [OK]

Hint: Think of a box inside another box holding related info [OK]

Common Mistakes:

• Confusing embedded documents with references
• Thinking embedded documents are separate collections
• Assuming embedded documents are stored outside the database

2. Which of the following is the correct way to insert an embedded document in MongoDB?

easy

A. db.collection.insertOne([{name: 'Alice'}, {address: {city: 'NY', zip: 10001}}])

B. db.collection.insertOne({name: 'Alice'}, {address: {city: 'NY', zip: 10001}})

C. db.collection.insertOne(name: 'Alice', address: {city: 'NY', zip: 10001})

D. db.collection.insertOne({name: 'Alice', address: {city: 'NY', zip: 10001}})

Solution

1. Step 1: Review MongoDB insertOne syntax

   insertOne takes a single document object with fields and values, including nested objects.

2. Step 2: Check each option's syntax

   db.collection.insertOne({name: 'Alice', address: {city: 'NY', zip: 10001}}) correctly nests the address object inside the main document. Others have syntax errors or wrong structure.

3. Final Answer:

   db.collection.insertOne({name: 'Alice', address: {city: 'NY', zip: 10001}}) -> Option D

4. Quick Check:

   Nested object inside one document = correct insert [OK]

Hint: Use one object with nested braces for embedded docs [OK]

Common Mistakes:

• Passing multiple objects instead of one
• Missing curly braces around nested document
• Using array instead of object for embedded document

3. Given the document { name: 'Bob', contact: { email: '[e-mail]', phone: '1234' } }, what will the query db.users.find({ 'contact.email': '[e-mail]' }) return?

medium

A. No documents, because nested fields can't be queried

B. All documents where contact.email equals '[e-mail]'

C. Documents where name equals '[e-mail]'

D. Documents where contact is exactly '[e-mail]'

Solution

1. Step 1: Understand dot notation in queries

   MongoDB uses dot notation to query fields inside embedded documents.

2. Step 2: Analyze the query

   The query looks for documents where the embedded field contact.email matches the given value.

3. Final Answer:

   All documents where contact.email equals '[e-mail]' -> Option B

4. Quick Check:

   Dot notation queries embedded fields correctly [OK]

Hint: Use dot notation to access nested fields in queries [OK]

Common Mistakes:

• Trying to match entire embedded document instead of field
• Using wrong field name without dot notation
• Assuming nested fields can't be queried

4. What is wrong with this update query to change the city in an embedded address document?
db.users.updateOne({name: 'Eve'}, {address.city: 'LA'})

medium

A. The field name should not use dot notation

B. The query filter is incorrect

C. The update document is missing the $set operator

D. updateOne cannot update embedded documents

Solution

1. Step 1: Recall updateOne syntax

   updateOne requires an update operator like $set to specify fields to change.

2. Step 2: Identify missing $set operator

   The query tries to update address.city directly without $set, which is invalid syntax.

3. Final Answer:

   The update document is missing the $set operator -> Option C

4. Quick Check:

   Updates need $set for field changes [OK]

Hint: Always use $set to update fields, including nested ones [OK]

Common Mistakes:

• Forgetting $set in update document
• Using dot notation incorrectly in filter
• Thinking updateOne can't change nested fields

5. You want to store multiple phone numbers inside a user's document using embedded documents. Which schema design is best?

hard

A. { name: 'Sam', phones: [{ type: 'home', number: '111' }, { type: 'work', number: '222' }] }

B. { name: 'Sam', phone1: '111', phone2: '222' }

C. { name: 'Sam', phones: { home: '111', work: '222' } }

D. { name: 'Sam', phones: '111,222' }

Solution

1. Step 1: Understand storing multiple embedded documents

   To store multiple related items, use an array of embedded documents for flexibility and clarity.

2. Step 2: Compare options

   { name: 'Sam', phones: [{ type: 'home', number: '111' }, { type: 'work', number: '222' }] } uses an array of objects with type and number, which is clear and scalable. Others are less flexible or harder to query.

3. Final Answer:

   { name: 'Sam', phones: [{ type: 'home', number: '111' }, { type: 'work', number: '222' }] } -> Option A

4. Quick Check:

   Array of embedded docs best for multiple related items [OK]

Hint: Use arrays of objects for multiple related embedded documents [OK]

Common Mistakes:

• Storing multiple values as comma-separated string
• Using separate fields for each phone number
• Using a single object without array for multiple items