Substring and overlay functions in PostgreSQL - Time & Space Complexity

Time Complexity: Substring and overlay functions

O(n)

Understanding Time Complexity

We want to understand how the time to extract or replace parts of text grows as the text gets longer.

How does the work change when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT substring(text_column FROM 5 FOR 10) AS part,
       overlay(text_column PLACING 'new' FROM 3 FOR 4) AS replaced
FROM example_table;
    

This code extracts a part of the text and replaces a part of the text in each row.

Identify Repeating Operations

Look for repeated work done by the functions.

• Primary operation: Scanning the input string to find and extract or replace the substring.
• How many times: Once per row in the table, each operation processes a portion of the string.

How Execution Grows With Input

As the input string gets longer, the functions need to look through more characters.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The work grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to extract or replace grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "Substring and overlay run instantly no matter how long the string is."

[OK] Correct: The functions must check characters to find the right part, so longer strings take more time.

Interview Connect

Understanding how string functions scale helps you write efficient queries and explain performance clearly.

Self-Check

"What if we used substring with a pattern match instead of fixed positions? How would the time complexity change?"