Recursive CTE concept in SQL - Time & Space Complexity

Time Complexity: Recursive CTE concept

O(n)

Understanding Time Complexity

Recursive CTEs run queries repeatedly to build results step-by-step.

We want to know how the work grows as the recursion goes deeper.

Scenario Under Consideration

Analyze the time complexity of the following recursive CTE.

WITH RECURSIVE Numbers AS (
  SELECT 1 AS num
  UNION ALL
  SELECT num + 1 FROM Numbers WHERE num < 6
)
SELECT * FROM Numbers;

This query generates numbers from 1 to 6 by repeatedly adding 1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive step that adds 1 to the number.
• How many times: Once per number from 1 up to 6 (6 times).

How Execution Grows With Input

Each recursion adds one more number until the limit is reached.

Input Size (n)	Approx. Operations
10	About 10 steps (including base)
100	About 100 steps
1000	About 1000 steps

Pattern observation: The number of steps grows roughly the same as the input size.

Final Time Complexity

Time Complexity: O(n)

This means the work grows linearly as the recursion depth increases.

Common Mistake

[X] Wrong: "Recursive CTEs run in constant time regardless of input size."

[OK] Correct: Each recursive step adds work, so more input means more steps and more time.

Interview Connect

Understanding recursive CTE time helps you explain how queries scale and shows you can reason about repeated work.

Self-Check

"What if the recursive step added two numbers each time instead of one? How would the time complexity change?"