Recursive CTEs in MySQL - Time & Space Complexity

Time Complexity: Recursive CTEs

O(n)

Understanding Time Complexity

Recursive CTEs run queries that call themselves repeatedly to build results step by step.

We want to know how the time needed grows as the data or recursion depth grows.

Scenario Under Consideration

Analyze the time complexity of the following recursive CTE in MySQL.

WITH RECURSIVE numbers AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 FROM numbers WHERE n < 5
)
SELECT * FROM numbers;
    

This query generates numbers from 1 to 5 by repeatedly adding 1 until it reaches 5.

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: The recursion runs once for each number from 1 up to 5.

How Execution Grows With Input

Each recursive call adds one more number until the limit is reached.

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

Pattern observation: The number of operations grows directly with the number of recursive steps.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows linearly as the recursion depth or input size increases.

Common Mistake

[X] Wrong: "Recursive CTEs run all steps at once, so time stays the same no matter the input size."

[OK] Correct: Each recursive step depends on the previous one, so the query runs more steps as the input grows, increasing time.

Interview Connect

Understanding recursive CTE time helps you explain how queries scale and shows you can reason about complex SQL operations.

Self-Check

"What if we changed the recursion to add 2 each time instead of 1? How would the time complexity change?"