Time Complexity: Pattern matching with template literals
O(1)
0
0
Pattern matching with template literals in Typescript - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to match patterns using template literals changes as the input grows.
How does the matching process scale when the input string gets longer?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
const input = "user_1234";
function matchUser(input: string): boolean {
return input.startsWith("user_");
}
console.log(matchUser(input));
This code checks if the input string starts with "user_" using a fixed prefix.
Identify Repeating Operations
- Primary operation: Checking each character of the prefix "user_" against the input string.
- How many times: Once per character in the prefix, which is a fixed length (5 characters).
How Execution Grows With Input
The check only looks at the first few characters, so even if the input grows, the work stays the same.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 5 (fixed prefix length) |
| 100 | 5 (still just prefix length) |
| 1000 | 5 (no change) |
Pattern observation: The number of operations does not grow with input size because only the fixed prefix is checked.
Final Time Complexity
Time Complexity: O(1)
This means the time to check the pattern stays the same no matter how long the input string is.
Common Mistake
[X] Wrong: "Matching a pattern with template literals always takes longer as the input grows."
[OK] Correct: Here, only the fixed part of the pattern is checked, so the input length does not affect the time.
Interview Connect
Understanding how pattern matching scales helps you explain your code's efficiency clearly and confidently in interviews.
Self-Check
"What if the pattern included a variable-length part that must be fully checked? How would the time complexity change?"