Array update with positional $ operator in MongoDB - Time & Space Complexity

Time Complexity: Array update with positional $ operator

O(n)

Understanding Time Complexity

When updating an element inside an array in MongoDB, it's important to understand how the time taken grows as the array gets bigger.

We want to know how the update operation scales when using the positional $ operator.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.collection.updateOne(
  { _id: 1, "items.id": 42 },
  { $set: { "items.$.value": 100 } }
)
    

This code finds a document with _id 1 and updates the value of the first array element in items where id is 42.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the items array to find the first element matching id: 42.
• How many times: In the worst case, it checks each element once until it finds a match or reaches the end.

How Execution Grows With Input

The time to find the matching array element grows as the array gets longer.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of checks grows directly with 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.

Common Mistake

[X] Wrong: "The positional $ operator updates the array element instantly regardless of array size."

[OK] Correct: MongoDB must scan the array to find the matching element first, so larger arrays take more time.

Interview Connect

Understanding how array updates scale helps you explain database performance clearly and shows you know how data size affects operations.

Self-Check

What if we added an index on items.id? How would the time complexity of this update change?