$push accumulator for building arrays in MongoDB - Time & Space Complexity

Time Complexity: $push accumulator for building arrays

O(n)

Understanding Time Complexity

We want to understand how the time needed to build arrays using the $push accumulator changes as the input data grows.

Specifically, how does adding elements to arrays during aggregation scale with more data?

Scenario Under Consideration

Analyze the time complexity of the following MongoDB aggregation snippet using $push.

db.orders.aggregate([
  { $group: {
      _id: "$customerId",
      items: { $push: "$item" }
    }
  }
])

This groups orders by customer and builds an array of items each customer ordered.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Adding each order's item to the customer's array using $push.
• How many times: Once for every order document processed.

How Execution Grows With Input

As the number of orders grows, the number of pushes grows the same way.

Input Size (n)	Approx. Operations
10	10 pushes to arrays
100	100 pushes to arrays
1000	1000 pushes to arrays

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

Final Time Complexity

Time Complexity: O(n)

This means the time to build the arrays grows linearly as more documents are processed.

Common Mistake

[X] Wrong: "Using $push is instant and does not depend on input size."

[OK] Correct: Each $push adds one element per document, so more documents mean more pushes and more time.

Interview Connect

Understanding how accumulators like $push scale helps you explain data aggregation efficiency clearly in real projects.

Self-Check

What if we replaced $push with $addToSet? How would the time complexity change?