Array of embedded documents queries in MongoDB - Time & Space Complexity

Time Complexity: Array of embedded documents queries

O(n * m)

Understanding Time Complexity

When querying arrays inside documents in MongoDB, it's important to know how the query time changes as the data grows.

We want to understand how the number of operations grows when searching embedded arrays.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB query.

db.orders.find({
  items: { $elemMatch: { productId: 123, quantity: { $gt: 2 } } }
})
.limit(5)

This query searches for orders where the items array has at least one element with productId 123 and quantity greater than 2, returning up to 5 results.

Identify Repeating Operations

Look for repeated checks inside the array of embedded documents.

• Primary operation: Scanning each document's items array to check each embedded document for matching conditions.
• How many times: For each order document, the query examines each item in the items array until it finds a match or reaches the end.

How Execution Grows With Input

As the number of orders and the size of each items array grow, the query checks more embedded documents.

Input Size (n)	Approx. Operations
10 orders with 5 items each	Up to 50 item checks
100 orders with 10 items each	Up to 1,000 item checks
1,000 orders with 20 items each	Up to 20,000 item checks

Pattern observation: The total checks grow roughly with the number of orders times the average number of items per order.

Final Time Complexity

Time Complexity: O(n * m)

This means the query time grows proportionally with the number of documents (n) times the average size of the embedded array (m).

Common Mistake

[X] Wrong: "The query only checks one item per document, so it runs in O(n)."

[OK] Correct: The query must check each item in the array until it finds a match, so it depends on the array size too, making it O(n * m).

Interview Connect

Understanding how queries on embedded arrays scale helps you design efficient data models and write performant queries, a valuable skill in real projects.

Self-Check

What if we added an index on the embedded document fields? How would the time complexity change?