Graph lookup for recursive data in MongoDB - Time & Space Complexity

Time Complexity: Graph lookup for recursive data

O(n)

Understanding Time Complexity

When working with recursive data in MongoDB, we often use graph lookup to find connected items.

We want to understand how the time needed grows as the data size and connections increase.

Scenario Under Consideration

Analyze the time complexity of the following MongoDB graph lookup query.

db.employees.aggregate([
  {
    $graphLookup: {
      from: "employees",
      startWith: "$_id",
      connectFromField: "managerId",
      connectToField: "_id",
      as: "managementChain"
    }
  }
])
    

This query finds all managers above an employee by recursively following the managerId field.

Identify Repeating Operations

Look for repeated steps in the query execution.

• Primary operation: Recursively searching connected documents by following managerId links.
• How many times: Once per level of management chain until no more managers are found.

How Execution Grows With Input

The query explores each connected document in the chain, so more levels mean more work.

Input Size (n)	Approx. Operations
10	About 10 lookups if chain is long
100	Up to 100 lookups if chain is long
1000	Up to 1000 lookups if chain is long

Pattern observation: The work grows roughly linearly with the length of the recursive chain.

Final Time Complexity

Time Complexity: O(n)

This means the time grows in direct proportion to the number of connected documents found in the recursion.

Common Mistake

[X] Wrong: "Graph lookup always runs in constant time because it uses indexes."

[OK] Correct: Even with indexes, the query must visit each connected document, so time grows with the chain length.

Interview Connect

Understanding how recursive queries scale helps you explain data retrieval in hierarchical structures clearly and confidently.

Self-Check

"What if the graph lookup had a maxDepth limit? How would that affect the time complexity?"