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?"

Practice

1. What does the MySQL function LOCATE('cat', 'concatenate') return?

easy

A. 0

B. 4

C. 1

D. 7

Solution

1. Step 1: Understand LOCATE function behavior

   LOCATE returns the position of the first occurrence of the substring in the string, starting from the beginning by default.

2. Step 2: Find 'cat' in 'concatenate'

   The substring 'cat' starts at the 4th character in 'concatenate'.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   LOCATE('cat', 'concatenate') = 4 [OK]

Hint: LOCATE returns first position of substring, counting from 1 [OK]

Common Mistakes:

• Counting from 0 instead of 1
• Confusing LOCATE with INSTR starting position
• Assuming substring not found returns NULL

2. Which of the following is the correct syntax to find the position of 'dog' in the string 'bulldog' starting search from position 5 using LOCATE?

easy

A. LOCATE('dog', 'bulldog') FROM 5

B. LOCATE('dog', 5, 'bulldog')

C. LOCATE('bulldog', 'dog', 5)

D. LOCATE('dog', 'bulldog', 5)

Solution

1. Step 1: Recall LOCATE syntax

   The correct syntax is LOCATE(substring, string, start_position).

2. Step 2: Match syntax with options

   LOCATE('dog', 'bulldog', 5) matches the correct order: substring 'dog', string 'bulldog', start position 5.

3. Final Answer:

   LOCATE('dog', 'bulldog', 5) -> Option D

4. Quick Check:

   LOCATE(substring, string, start) correct syntax [OK]

Hint: LOCATE syntax: substring, string, start position [OK]

Common Mistakes:

• Swapping string and substring order
• Using incorrect argument order
• Trying to use FROM keyword

3. What is the output of this query?

SELECT INSTR('hello world', 'o');

medium

A. 6

B. 8

C. 0

D. 5

Solution

1. Step 1: Understand INSTR function behavior

   INSTR returns the position of the first occurrence of the substring in the string, starting from the beginning.

2. Step 2: Find 'o' in 'hello world'

   The first 'o' appears at the 6th character in 'hello world'.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   INSTR('hello world', 'o') = 6 [OK]

Hint: INSTR always starts searching from beginning [OK]

Common Mistakes:

• Choosing position of second 'o' instead of first
• Confusing INSTR with LOCATE with start position
• Assuming zero-based index

4. Identify the error in this query:

SELECT LOCATE('test', 'testing', 0);

medium

A. Start position cannot be zero; must be >= 1

B. String and substring arguments are swapped

C. No error; query is valid

D. LOCATE does not accept three arguments

Solution

1. Step 1: Check LOCATE start position rules

   The start position argument can be less than 1; it is treated as 1 with no error.

2. Step 2: Analyze the query

   The query uses 0 as start position, which is valid; the search starts from position 1.

3. Final Answer:

   No error; query is valid -> Option C

4. Quick Check:

   LOCATE start position <1 clamped to 1 [OK]

Hint: LOCATE start_position <1 is allowed, search starts from 1 [OK]

Common Mistakes:

• Believing start position must be >=1 (it's clamped if less)
• Confusing argument order
• Assuming LOCATE uses zero-based indexing

5. Given the string 'abracadabra', which query returns the position of the second occurrence of 'a' using LOCATE?

hard

A. SELECT LOCATE('a', 'abracadabra', LOCATE('a', 'abracadabra') + 1);

B. SELECT INSTR('abracadabra', 'a', 2);

C. SELECT LOCATE('a', 'abracadabra', 5);

D. SELECT LOCATE('a', 'abracadabra', 1);

Solution

1. Step 1: Find first occurrence of 'a'

   LOCATE('a', 'abracadabra') returns 1, the position of the first 'a'.

2. Step 2: Use LOCATE with start position after first 'a'

   To find the second 'a', start searching from position 2 (1 + 1) using LOCATE('a', 'abracadabra', 2).

3. Step 3: Combine steps in one query

   Use nested LOCATE: LOCATE('a', 'abracadabra', LOCATE('a', 'abracadabra') + 1) to get second occurrence.

4. Final Answer:

   SELECT LOCATE('a', 'abracadabra', LOCATE('a', 'abracadabra') + 1); -> Option A

5. Quick Check:

   Nested LOCATE finds second occurrence [OK]

Hint: Use nested LOCATE with start = first position + 1 [OK]

Common Mistakes:

• Using INSTR with start position (not supported)
• Starting search at wrong position
• Not adding 1 to first occurrence position