Array expressions ($size, $arrayElemAt, $filter) in MongoDB - Time & Space Complexity

Time Complexity: Array expressions ($size, $arrayElemAt, $filter)

O(n)

Understanding Time Complexity

When working with arrays in MongoDB, it's important to know how the time to process them grows as the array gets bigger.

We want to understand how operations like counting elements, picking one element, or filtering affect performance as the array size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    db.collection.aggregate([
      {
        $project: {
          totalItems: { $size: "$items" },
          firstItem: { $arrayElemAt: ["$items", 0] },
          filteredItems: { $filter: {
            input: "$items",
            as: "item",
            cond: { $gt: ["$$item.price", 100] }
          }}
        }
      }
    ])
    

This code counts the number of items, gets the first item, and filters items with price over 100 in each document.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the array to filter items.
• How many times: The filter checks each element once, so it runs once per item in the array.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 10 checks for filtering, plus 1 for size and 1 for first element
100	About 100 checks for filtering, plus 1 for size and 1 for first element
1000	About 1000 checks for filtering, plus 1 for size and 1 for first element

Pattern observation: The filtering work grows directly with the number of items, while size and first element are quick constant-time operations.

Final Time Complexity

Time Complexity: O(n)

This means the time to run this aggregation grows linearly with the number of items in the array.

Common Mistake

[X] Wrong: "Getting the size or first element of an array takes as long as filtering all items."

[OK] Correct: Counting elements or picking one element is very fast and does not depend on array size, unlike filtering which checks each item.

Interview Connect

Understanding how array operations scale helps you write efficient queries and explain your choices clearly in interviews.

Self-Check

"What if we changed the filter condition to check nested arrays inside each item? How would the time complexity change?"