LOCATE and INSTR in MySQL - Time & Space Complexity

Time Complexity: LOCATE and INSTR

O(n)

Understanding Time Complexity

We want to understand how the time it takes to find a substring in a string grows as the string gets longer.

How does searching for a smaller word inside a bigger sentence affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT LOCATE('cat', description) AS position
FROM products;

SELECT INSTR(description, 'cat') AS position
FROM products;
    

This code finds the position of the word 'cat' inside the 'description' text for each product.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the description string character by character to find the substring.
• How many times: Up to the length of the description string for each product.

How Execution Grows With Input

As the description gets longer, the search takes more steps because it checks more characters.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to find the substring grows linearly with the length of the string.

Common Mistake

[X] Wrong: "LOCATE and INSTR instantly find the substring no matter how long the string is."

[OK] Correct: The functions must check characters one by one, so longer strings take more time.

Interview Connect

Understanding how substring search time grows helps you explain performance in real database queries.

Self-Check

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