Upsert behavior (update or insert) in MongoDB - Time & Space Complexity

Time Complexity: Upsert behavior (update or insert)

O(log n)

Understanding Time Complexity

When using upsert in MongoDB, we want to know how the time to complete the operation changes as the data grows.

We ask: How does MongoDB find and update or insert a document as the collection gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.collection.updateOne(
  { _id: 123 },
  { $set: { name: "Alice" } },
  { upsert: true }
)
    

This code tries to find a document with _id 123. If found, it updates the name. If not, it inserts a new document with _id 123 and name "Alice".

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Searching the collection for a document matching the filter {_id: 123}.
• How many times: This search happens once per upsert operation.

How Execution Grows With Input

As the collection grows, finding the document can take longer if there is no index on _id.

Input Size (n)	Approx. Operations
10	About 10 checks if no index
100	About 100 checks if no index
1000	About 1000 checks if no index

Pattern observation: Without an index, the search grows linearly with the number of documents. With an index, the search is much faster and does not grow linearly.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find and update or insert a document grows slowly as the collection grows, thanks to indexing.

Common Mistake

[X] Wrong: "Upsert always takes the same time no matter how big the collection is."

[OK] Correct: The time depends on how MongoDB finds the document. Without an index, it checks many documents, so it takes longer as the collection grows.

Interview Connect

Understanding how upsert works and its time cost helps you explain database efficiency clearly and confidently in real-world situations.

Self-Check

"What if we removed the index on _id? How would the time complexity of the upsert change?"