Recursive CTE for hierarchical data in SQL - Time & Space Complexity

Time Complexity: Recursive CTE for hierarchical data

O(n)

Understanding Time Complexity

When working with hierarchical data, recursive queries help us find all related items step-by-step.

We want to know how the time to get all related data grows as the hierarchy gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

WITH RECURSIVE Subordinates AS (
  SELECT employee_id, manager_id, name
  FROM employees
  WHERE manager_id IS NULL
  UNION ALL
  SELECT e.employee_id, e.manager_id, e.name
  FROM employees e
  INNER JOIN Subordinates s ON e.manager_id = s.employee_id
)
SELECT * FROM Subordinates;

This query finds all employees under top-level managers by repeatedly joining employees to their managers.

Identify Repeating Operations

• Primary operation: Recursive join between employees and the growing set of subordinates.
• How many times: Once for each level of the hierarchy until all subordinates are found.

How Execution Grows With Input

Each recursion step adds employees reporting to the current level, repeating until no more are found.

Input Size (n)	Approx. Operations
10	About 10 joins, one per employee
100	About 100 joins, growing with employees
1000	About 1000 joins, scaling with total employees

Pattern observation: The work grows roughly in proportion to the total number of employees processed.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of employees in the hierarchy.

Common Mistake

[X] Wrong: "Recursive queries always take exponential time because they repeat joins many times."

[OK] Correct: Each employee is processed once in the recursion, so the total work grows linearly, not exponentially.

Interview Connect

Understanding recursive queries shows you can handle complex data relationships, a useful skill in many real projects.

Self-Check

"What if the hierarchy has cycles? How would that affect the time complexity of the recursive query?"