$in for matching a set in MongoDB - Time & Space Complexity

Time Complexity: $in for matching a set

O(n)

Understanding Time Complexity

When using $in in MongoDB, we want to know how the time to find matching documents changes as the list of values grows.

We ask: How does the number of operations grow when the set inside $in gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following MongoDB query using $in.

db.collection.find({
  field: { $in: [value1, value2, value3, ..., valueN] }
})
    

This query finds documents where the field matches any value in the given list.

Identify Repeating Operations

Look at what repeats inside the query process.

• Primary operation: Checking if the document's field matches any value in the $in list.
• How many times: Once for each document scanned, checking against the list of values.

How Execution Grows With Input

As the list inside $in grows, the work to check each document grows too.

Input Size (n)	Approx. Operations
10	Checking up to 10 values per document
100	Checking up to 100 values per document
1000	Checking up to 1000 values per document

Pattern observation: The number of checks grows directly with the size of the $in list.

Final Time Complexity

Time Complexity: O(n)

This means the time to match grows linearly with the number of values inside the $in list.

Common Mistake

[X] Wrong: "Using $in with many values is always fast because MongoDB handles it internally."

[OK] Correct: MongoDB checks each value in the list, so a bigger list means more work and slower queries if no index supports it.

Interview Connect

Understanding how $in scales helps you explain query performance clearly and shows you know how database operations grow with input size.

Self-Check

"What if we replaced $in with multiple $or conditions? How would the time complexity change?"