SUBSTRING and LEFT/RIGHT in MySQL - Time & Space Complexity

Time Complexity: SUBSTRING and LEFT/RIGHT

O(k * n)

Understanding Time Complexity

When working with text data in databases, we often extract parts of strings using functions like SUBSTRING, LEFT, and RIGHT.

We want to understand how the time it takes to run these functions changes as the size of the input text grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT 
  SUBSTRING(description, 1, 10) AS first_ten_chars,
  LEFT(description, 5) AS first_five_chars,
  RIGHT(description, 5) AS last_five_chars
FROM products;
    

This code extracts parts of the 'description' text from each product: the first 10 characters, the first 5 characters, and the last 5 characters.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Extracting a substring from each string in the 'description' column.
• 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 string.

Input Size (length of description)	Approx. Operations per row
10	About 10 operations (extracting 10 chars)
100	Still about 10 operations (only first 10 chars extracted)
1000	Still about 10 operations (fixed substring length)

Pattern observation: The time to extract a fixed substring stays about the same no matter how long the full string is.

Final Time Complexity

Time Complexity: O(k * n)

This means the time grows linearly with the number of rows (n), and with the fixed substring length (k), which is usually small and constant.

Common Mistake

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

[OK] Correct: Since we only extract a fixed number of characters, the operation depends on that fixed length, not the entire string size.

Interview Connect

Understanding how string functions scale helps you write efficient queries and explain performance in interviews confidently.

Self-Check

"What if we extract a substring whose length depends on the full string length? How would the time complexity change?"