Common patterns and character classes in Ruby - Time & Space Complexity

Time Complexity: Common patterns and character classes

O(n)

Understanding Time Complexity

When using common patterns and character classes in Ruby regular expressions, it's important to understand how the matching process scales as the input grows.

We want to know how the time to find matches changes when the text gets longer.

Scenario Under Consideration

Analyze the time complexity of the following Ruby code snippet.

text = "a1b2c3d4e5"
pattern = /[a-z]\d/
matches = text.scan(pattern)
puts matches
    

This code finds all pairs where a lowercase letter is followed by a digit in the given text.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The scan method checks each position in the text to see if the pattern matches starting there.
• How many times: It tries matching at every character index, so roughly once per character in the text.

How Execution Grows With Input

As the text gets longer, the number of checks grows roughly in direct proportion to the text length.

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 input grows, roughly one check per character.

Final Time Complexity

Time Complexity: O(n)

This means the time to find matches grows in a straight line with the size of the input text.

Common Mistake

[X] Wrong: "Using character classes makes the search instant regardless of input size."

[OK] Correct: Even with character classes, the program still checks each position in the text, so time grows with input length.

Interview Connect

Understanding how pattern matching scales helps you write efficient code and explain your reasoning clearly in interviews.

Self-Check

"What if the pattern included a quantifier like + or *? How would the time complexity change?"