$addToSet for unique array additions in MongoDB - Time & Space Complexity

Time Complexity: $addToSet for unique array additions

O(n)

Understanding Time Complexity

When using $addToSet in MongoDB, it is important to understand how the time it takes to add unique items grows as the array gets bigger.

We want to know how the cost changes when the array inside a document grows in size.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB update operation.

db.collection.updateOne(
  { _id: 1 },
  { $addToSet: { tags: "newTag" } }
)
    

This code adds "newTag" to the tags array only if it is not already present.

Identify Repeating Operations

Look for operations that repeat or grow with input size.

• Primary operation: Checking if the value already exists in the tags array.
• How many times: The check scans through the array elements one by one until it finds a match or reaches the end.

How Execution Grows With Input

As the tags array grows, the time to check for duplicates grows too.

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 roughly in direct proportion to the array size.

Final Time Complexity

Time Complexity: O(n)

This means the time to add a unique item grows linearly with the size of the array.

Common Mistake

[X] Wrong: "Adding with $addToSet is always fast and constant time regardless of array size."

[OK] Correct: MongoDB must check each element to avoid duplicates, so the time grows as the array gets bigger.

Interview Connect

Understanding how $addToSet scales helps you explain database update costs clearly and shows you know how data size affects performance.

Self-Check

What if the tags array was indexed or stored as a set type? How would the time complexity change?