Arrays in documents in MongoDB - Time & Space Complexity

Time Complexity: Arrays in documents

O(n)

Understanding Time Complexity

When working with arrays inside MongoDB documents, it's important to understand how the time to process these arrays grows as they get bigger.

We want to know how the number of operations changes when we query or update arrays inside documents.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Find documents where the array contains a specific value
db.collection.find({ tags: "mongodb" })

// Update: add a new tag to the array
 db.collection.updateOne(
   { _id: 1 },
   { $push: { tags: "database" } }
 )
    

This code searches for documents with a specific value inside an array and adds a new value to an array in a document.

Identify Repeating Operations

Look for repeated steps that take time.

• Primary operation: Scanning the array inside each document to check for the value or to add a new element.
• How many times: For each document, the array elements are checked one by one until the value is found or the end is reached.

How Execution Grows With Input

As the array inside documents grows, the time to check or update grows too.

Input Size (n)	Approx. Operations
10	About 10 checks or steps
100	About 100 checks or steps
1000	About 1000 checks or steps

Pattern observation: The time grows roughly in direct proportion to the array size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find or update an element grows linearly with the number of items in the array.

Common Mistake

[X] Wrong: "Searching inside an array in a document is always fast and constant time."

[OK] Correct: MongoDB must check each element until it finds the match, so time grows with array size, not constant.

Interview Connect

Understanding how array size affects query and update time helps you explain real-world database behavior clearly and confidently.

Self-Check

"What if the array is indexed with a multikey index? How would the time complexity change for searching inside the array?"