REPLACE function in SQL - Time & Space Complexity

Time Complexity: REPLACE function

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run the REPLACE function changes as the size of the text grows.

How does the work inside REPLACE grow when the input string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT REPLACE(description, 'old', 'new') AS updated_description
FROM products;
    

This code replaces every occurrence of the word 'old' with 'new' in the description column for all products.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each character of the description string to find matches of 'old'.
• How many times: Once for each character in the string, repeated for every row in the table.

How Execution Grows With Input

As the length of the description grows, the time to scan and replace grows roughly in direct proportion.

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

Pattern observation: The work grows linearly as the string gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to run REPLACE grows in a straight line with the length of the input string.

Common Mistake

[X] Wrong: "REPLACE runs instantly no matter how long the string is."

[OK] Correct: The function must check each character to find matches, so longer strings take more time.

Interview Connect

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

Self-Check

"What if we replaced a longer substring instead of a short one? How would the time complexity change?"