Pattern matching with LIKE and ILIKE in PostgreSQL - Time & Space Complexity

Time Complexity: Pattern matching with LIKE and ILIKE

O(n)

Understanding Time Complexity

When we use pattern matching with LIKE or ILIKE in PostgreSQL, the database checks each row to see if the text matches the pattern.

We want to understand how the time it takes grows as the number of rows increases.

Scenario Under Consideration

Analyze the time complexity of the following query.

SELECT *
FROM products
WHERE name LIKE 'A%';
    

This query finds all products whose names start with the letter 'A'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row's 'name' column 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 must check more names against the pattern.

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

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

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "LIKE queries always use indexes and run fast regardless of table size."

[OK] Correct: If the pattern starts with a wildcard (like '%abc'), indexes usually can't help, so the database checks every row, making the query slower as the table grows.

Interview Connect

Understanding how pattern matching scales helps you explain query performance clearly and shows you know how databases work under the hood.

Self-Check

"What if we changed the pattern from 'A%' to '%A'? How would the time complexity change and why?"