$all operator for matching all elements in MongoDB - Time & Space Complexity

Time Complexity: $all operator for matching all elements

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to run a MongoDB query using the $all operator changes as the data grows.

Specifically, how does checking if a document's array contains all specified elements affect performance?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

db.collection.find({
  tags: { $all: ["red", "blue", "green"] }
})

This query finds documents where the tags array contains all three colors: red, blue, and green.

Identify Repeating Operations

Look at what repeats when MongoDB checks each document.

• Primary operation: Checking each document's tags array to see if it contains all specified elements.
• How many times: This check happens once per document in the collection or index scan.

How Execution Grows With Input

As the number of documents grows, MongoDB must check more arrays.

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

Pattern observation: The number of checks grows directly with the number of documents.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to run the query grows linearly with the number of documents and the number of elements to check in each array.

Common Mistake

[X] Wrong: "Using $all is always fast because it just checks a few elements."

[OK] Correct: MongoDB must check each document's array, so if there are many documents, it takes longer.

Interview Connect

Understanding how queries like $all scale helps you write better database queries and explain your choices clearly.

Self-Check

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