Recursive CTE for series generation in SQL - Time & Space Complexity

Time Complexity: Recursive CTE for series generation

O(n)

Understanding Time Complexity

When we use a recursive CTE to generate a series, we want to know how the work grows as the series gets longer.

We ask: How many steps does the database take as the number of items in the series increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code generates numbers from 1 up to 1000 using recursion.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive step that adds 1 to the previous number.
• How many times: This step repeats once for each number from 2 to 1000, so about 999 times.

How Execution Grows With Input

Each new number requires one recursive step, so the total steps grow directly with the size of the series.

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

Pattern observation: The number of steps grows in a straight line as the series gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the work grows directly in proportion to how many numbers we want to generate.

Common Mistake

[X] Wrong: "Recursive CTEs run in constant time no matter the series length."

[OK] Correct: Each recursive step adds one more number, so more numbers mean more steps and more work.

Interview Connect

Understanding how recursive queries grow helps you explain efficiency clearly and shows you know how databases handle repeated work.

Self-Check

"What if we changed the recursion to generate numbers by adding 2 each time instead of 1? How would the time complexity change?"