GENERATE_SERIES for sequence creation in PostgreSQL - Time & Space Complexity

Time Complexity: GENERATE_SERIES for sequence creation

O(n)

Understanding Time Complexity

We want to understand how the time to create a sequence using GENERATE_SERIES changes as the sequence length grows.

How does the number of generated values affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL query.

SELECT * FROM GENERATE_SERIES(1, 1000);
    

This query creates a list of numbers from 1 to 1000, one row per number.

Identify Repeating Operations

Look for repeated actions in the query.

• Primary operation: Generating each number in the sequence.
• How many times: Once for each number from start to end (e.g., 1000 times).

How Execution Grows With Input

The work grows directly with how many numbers we want to generate.

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

Pattern observation: Doubling the sequence length doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to generate the sequence grows in direct proportion to the number of values requested.

Common Mistake

[X] Wrong: "GENERATE_SERIES runs in constant time no matter how big the sequence is."

[OK] Correct: Each number must be created and returned, so more numbers mean more work.

Interview Connect

Understanding how sequence generation scales helps you reason about query performance and data size handling in real projects.

Self-Check

"What if we generate a sequence with a step size greater than 1? How would that affect the time complexity?"