Comparison expressions ($eq, $gt in aggregation) in MongoDB - Time & Space Complexity

Time Complexity: Comparison expressions ($eq, $gt in aggregation)

O(n)

Understanding Time Complexity

When using comparison expressions like $eq and $gt in MongoDB aggregation, it's important to understand how the time to run these checks grows as the data grows.

We want to know how the number of comparisons affects the total work done.

Scenario Under Consideration

Analyze the time complexity of the following aggregation pipeline snippet.

    db.collection.aggregate([
      { $match: { $expr: { $gt: ["$score", 50] } } },
      { $project: { name: 1, passed: { $eq: ["$status", "passed"] } } }
    ])
    

This pipeline filters documents where the score is greater than 50, then adds a field passed that is true if status equals "passed".

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The aggregation processes each document once, applying $gt and $eq comparisons.
• How many times: Each comparison runs once per document in the input collection.

How Execution Grows With Input

As the number of documents grows, the number of comparisons grows at the same rate.

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

Pattern observation: The work grows directly with the number of documents, doubling the documents doubles the comparisons.

Final Time Complexity

Time Complexity: O(n)

This means the time to run these comparisons grows in a straight line with the number of documents.

Common Mistake

[X] Wrong: "Comparison expressions like $eq and $gt run once and don't depend on data size."

[OK] Correct: Each document must be checked, so the number of comparisons grows with the number of documents.

Interview Connect

Understanding how comparison operations scale helps you explain query performance clearly and shows you know how MongoDB processes data step-by-step.

Self-Check

"What if we added a $lookup stage before the $match? How would that affect the time complexity of the comparison expressions?"