Named captures in Ruby - Time & Space Complexity

Time Complexity: Named captures

O(n)

Understanding Time Complexity

We want to understand how the time it takes to find named parts in text grows as the text gets longer.

How does the work change when we use named captures in Ruby regular expressions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "Name: John, Age: 30; Name: Jane, Age: 25"
pattern = /Name: (?\w+), Age: (?\d+)/

text.scan(pattern) do
  name = Regexp.last_match[:name]
  age = Regexp.last_match[:age]
  # process name and age
end
    

This code finds all name and age pairs in a string using named captures in a regular expression.

Identify Repeating Operations

• Primary operation: The scan method loops through the text to find matches.
• How many times: It runs once for each match found in the text.

How Execution Grows With Input

As the text gets longer, the number of matches usually grows too, so the work grows with the text size.

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

Pattern observation: The work grows roughly in direct proportion to the length of the text.

Final Time Complexity

Time Complexity: O(n)

This means the time to find named captures grows linearly as the text gets longer.

Common Mistake

[X] Wrong: "Using named captures makes the search slower by a lot."

[OK] Correct: Named captures add only a small, constant amount of work per match, so the overall time still grows mainly with the text size.

Interview Connect

Understanding how pattern matching scales helps you write efficient text processing code, a useful skill in many programming tasks.

Self-Check

"What if we changed the pattern to use unnamed captures instead? How would the time complexity change?"