Array update with $[identifier] filtered in MongoDB - Time & Space Complexity

Time Complexity: Array update with $[identifier] filtered

O(n)

Understanding Time Complexity

When updating elements inside an array in MongoDB using the $[identifier] filtered positional operator, it's important to understand how the operation's cost changes as the array grows.

We want to know how the time to update scales when the array inside documents gets larger.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB update operation.

db.collection.updateMany(
  { "items.status": "pending" },
  { $set: { "items.$[elem].status": "complete" } },
  { arrayFilters: [ { "elem.status": "pending" } ] }
)
    

This code updates all documents where the array 'items' has elements with status 'pending'. It sets those elements' status to 'complete' using a filtered positional operator.

Identify Repeating Operations

Look at what repeats inside the update:

• Primary operation: Scanning each element in the 'items' array to check if it matches the filter condition.
• How many times: For each document matched, the operation checks every element in the 'items' array once.

How Execution Grows With Input

The time to update grows as the number of elements in the 'items' array grows.

Input Size (n)	Approx. Operations
10	About 10 checks per document
100	About 100 checks per document
1000	About 1000 checks per document

Pattern observation: The number of operations grows roughly in direct proportion to the array size.

Final Time Complexity

Time Complexity: O(n)

This means the update time grows linearly with the number of elements in the array being filtered.

Common Mistake

[X] Wrong: "The update only touches the matching elements, so it runs in constant time regardless of array size."

[OK] Correct: MongoDB must check each array element to find matches, so the time depends on how many elements there are, not just the matches.

Interview Connect

Understanding how array updates scale helps you explain database performance clearly and shows you know how MongoDB handles array filters under the hood.

Self-Check

What if we changed the array filter to match multiple fields or nested arrays? How would the time complexity change?