LIKE pattern matching in MySQL - Time & Space Complexity

Time Complexity: LIKE pattern matching

O(n)

Understanding Time Complexity

When searching text in a database, LIKE pattern matching helps find rows that fit a pattern.

We want to understand how the search time changes as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM products
WHERE product_name LIKE '%phone%';
    

This query finds all products with "phone" anywhere in their name.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row's product_name against the pattern.
• How many times: Once for every row in the products table.

How Execution Grows With Input

As the number of rows grows, the database checks more product names one by one.

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

Pattern observation: The work grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "LIKE with % in front is fast because it uses indexes."

[OK] Correct: When % is at the start, indexes usually can't help, so the database checks every row.

Interview Connect

Understanding how pattern searches scale helps you explain database performance clearly and confidently.

Self-Check

"What if the pattern was 'phone%' instead of '%phone%'? How would the time complexity change?"