$first and $last accumulators in MongoDB - Time & Space Complexity

Time Complexity: $first and $last accumulators

O(n log n)

Understanding Time Complexity

When using $first and $last accumulators in MongoDB aggregation, it's important to understand how the processing time changes as the data grows.

We want to know how the number of operations changes when the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB aggregation snippet.

db.collection.aggregate([
  { $sort: { category: 1, date: 1 } },
  { $group: {
      _id: "$category",
      firstEntry: { $first: "$value" },
      lastEntry: { $last: "$value" }
    }
  }
])

This code sorts documents by category and date, then groups by category to find the first and last values in each group.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Sorting all documents by category and date.
• How many times: The sort processes all n documents once.
• Grouping: Scans sorted documents once to find first and last per group.

How Execution Grows With Input

As the number of documents grows, the sorting step takes more time, while grouping scans through the sorted list once.

Input Size (n)	Approx. Operations
10	About 10 log 10 (sort) + 10 (group)
100	About 100 log 100 + 100
1000	About 1000 log 1000 + 1000

Pattern observation: The sorting dominates and grows a bit faster than the number of documents, while grouping grows linearly.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to run this aggregation grows a bit faster than the number of documents because of sorting.

Common Mistake

[X] Wrong: "$first and $last run in constant time regardless of input size."

[OK] Correct: While $first and $last themselves pick values quickly, the sorting step before grouping takes more time as data grows, affecting overall speed.

Interview Connect

Understanding how sorting affects aggregation helps you explain performance in real projects and shows you can think about data size impact clearly.

Self-Check

What if we removed the $sort stage before grouping? How would the time complexity change?