$nin for not in set in MongoDB - Time & Space Complexity

Time Complexity: $nin for not in set

O(n)

Understanding Time Complexity

When using $nin in MongoDB, we want to know how the time to find documents changes as the data grows.

We ask: How does checking for values not in a list affect the work MongoDB does?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.collection.find({
  field: { $nin: ["A", "B", "C"] }
})
.limit(100)

This query finds documents where the field value is not in the list ["A", "B", "C"].

Identify Repeating Operations

Look at what MongoDB does repeatedly to answer this query.

• Primary operation: Checking each document's field value against the $nin list.
• How many times: Once for each document scanned until 100 matches are found.

How Execution Grows With Input

As the number of documents grows, MongoDB checks more documents to find those not in the list.

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

Pattern observation: The work grows roughly in direct proportion to the number of documents MongoDB scans.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of documents MongoDB checks.

Common Mistake

[X] Wrong: "Using $nin is always fast because it just excludes a few values."

[OK] Correct: MongoDB may need to check many documents to confirm they are not in the list, especially without an index, so it can take time proportional to the data size.

Interview Connect

Understanding how $nin affects query time helps you explain real database behavior clearly and shows you think about efficiency in practical ways.

Self-Check

"What if we added an index on the field? How would the time complexity change?"