$min and $max accumulators in MongoDB - Time & Space Complexity

Time Complexity: $min and $max accumulators

O(n)

Understanding Time Complexity

When using $min and $max accumulators in MongoDB aggregation, it's important to know how the time to find minimum or maximum values grows as data grows.

We want to understand how the work changes when the number of documents increases.

Scenario Under Consideration

Analyze the time complexity of the following aggregation pipeline using $min and $max.

    db.sales.aggregate([
      {
        $group: {
          _id: "$store",
          minSale: { $min: "$amount" },
          maxSale: { $max: "$amount" }
        }
      }
    ])
    

This groups sales by store and finds the smallest and largest sale amount per store.

Identify Repeating Operations

Look for repeated work done by the query.

• Primary operation: Scanning each document once to compare its amount value.
• How many times: Once per document in the collection.

How Execution Grows With Input

As the number of documents grows, the number of comparisons grows roughly the same.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find minimum and maximum values grows linearly with the number of documents.

Common Mistake

[X] Wrong: "Using $min and $max is instant no matter how many documents there are."

[OK] Correct: MongoDB must check each document's value to find the min or max, so more documents mean more work.

Interview Connect

Understanding how accumulators like $min and $max scale helps you explain query performance clearly and shows you grasp how databases process data.

Self-Check

"What if we added an index on the amount field? How would that affect the time complexity of finding $min and $max?"