Time Complexity: Scan for all matches
O(n)
0
0
Scan for all matches in Ruby - Time & Space Complexity
Understanding Time Complexity
We want to understand how long it takes to find all matches of a pattern in a string.
How does the time needed grow as the string gets longer?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
text = "hello hello hello"
pattern = /hello/
matches = text.scan(pattern)
This code finds all occurrences of "hello" in the text string.
Identify Repeating Operations
- Primary operation: The scan method checks each position in the string to see if the pattern matches.
- How many times: It repeats this check for almost every character in the string.
How Execution Grows With Input
As the string gets longer, the number of checks grows roughly in direct proportion.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 checks |
| 100 | About 100 checks |
| 1000 | About 1000 checks |
Pattern observation: The work grows steadily as the string grows longer.
Final Time Complexity
Time Complexity: O(n)
This means the time to find all matches grows in a straight line with the string length.
Common Mistake
[X] Wrong: "The scan method only looks at the first few characters, so it's very fast regardless of string size."
[OK] Correct: Actually, scan checks the whole string to find all matches, so the time grows with the string length.
Interview Connect
Understanding how searching through text grows with input size helps you explain efficiency clearly and confidently.
Self-Check
"What if the pattern was more complex, like a nested group or optional parts? How would the time complexity change?"