Capture groups in Ruby - Time & Space Complexity

Time Complexity: Capture groups

O(n)

Understanding Time Complexity

When using capture groups in Ruby regular expressions, it is important to understand how the time to find matches grows as the input string gets longer.

We want to know how the work done by the regex engine changes with bigger inputs.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "abc123def456"
pattern = /(\d{3})/  # capture groups for 3 digits
matches = text.scan(pattern)
    

This code finds all groups of three digits in the text and stores them.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regex engine scans through the input string character by character to find matches.
• How many times: It checks each position in the string once, trying to match the pattern with capture groups.

How Execution Grows With Input

As the input string gets longer, the regex engine does more checks, roughly one per character.

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

Pattern observation: The work grows roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to find capture groups grows linearly as the input string gets longer.

Common Mistake

[X] Wrong: "Capture groups make the regex run much slower, like exponentially slower."

[OK] Correct: Simple capture groups add only a small fixed amount of work per match attempt, so the overall time still grows linearly with input size.

Interview Connect

Understanding how capture groups affect regex performance helps you write efficient pattern matching code, a useful skill in many programming tasks.

Self-Check

"What if the pattern used nested capture groups or backreferences? How would the time complexity change?"