Time Complexity: WHERE with LIKE pattern matching
O(n)
0
0
WHERE with LIKE pattern matching in SQL - Time & Space Complexity
Understanding Time Complexity
When using WHERE with LIKE in SQL, we want to know how the search time changes as the data grows.
How does the database find matching rows when using pattern matching?
Scenario Under Consideration
Analyze the time complexity of the following SQL query.
SELECT *
FROM employees
WHERE name LIKE 'A%';
This query finds all employees whose names start with the letter 'A'.
Identify Repeating Operations
Look for repeated checks or scans in the query.
- Primary operation: Checking each row's name against the pattern.
- How many times: Once per row in the employees table.
How Execution Grows With Input
As the number of employees grows, the database checks more names.
| 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 find matches grows in a straight line with the number of rows.
Common Mistake
[X] Wrong: "LIKE with a pattern always uses an index and is very fast."
[OK] Correct: If the pattern starts with a wildcard (like '%abc'), the database cannot use an index efficiently and must check every row.
Interview Connect
Understanding how pattern matching affects search time helps you explain database performance clearly and confidently.
Self-Check
"What if we changed the pattern to '%A'? How would the time complexity change?"