SUBSTRING extraction in SQL - Time & Space Complexity

Time Complexity: SUBSTRING extraction

O(k)

Understanding Time Complexity

When we extract parts of text from database fields, it is important to know how the work grows as the text gets longer.

We want to understand how the time to get a substring changes when the input text size changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT SUBSTRING(description, 1, 10) AS short_desc
FROM products;

This code extracts the first 10 characters from the "description" column for every product.

Identify Repeating Operations

• Primary operation: Extracting a substring from each text field.
• How many times: Once per row in the products table.

How Execution Grows With Input

Extracting a fixed-length substring takes time proportional to the length of the substring, not the full text.

Input Size (length of full text)	Approx. Operations
10	About 10 operations (extract 10 chars)
100	Still about 10 operations (only first 10 chars extracted)
1000	Still about 10 operations (substring length fixed)

Pattern observation: The time depends on the substring length, not the full text length.

Final Time Complexity

Time Complexity: O(k)

This means the time grows with the length of the substring extracted, which is fixed here, so it stays constant regardless of full text size.

Common Mistake

[X] Wrong: "Extracting a substring always takes time proportional to the full text length."

[OK] Correct: The operation only copies the requested substring length, so if that length is fixed, the time does not grow with the full text size.

Interview Connect

Understanding how substring extraction scales helps you reason about text processing in databases, a common task in real projects and interviews.

Self-Check

What if we changed the substring length to be the full length of the text? How would the time complexity change?