Regular expressions with Regex class in Kotlin - Time & Space Complexity

Time Complexity: Regular expressions with Regex class

O(n)

Understanding Time Complexity

We want to understand how the time it takes to check text with a regular expression changes as the text gets longer.

How does the work grow when we use Kotlin's Regex class on bigger input?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val pattern = Regex("a*b")
val input = "aaaaab"
val result = pattern.matches(input)
println(result)
    

This code checks if the input string matches the pattern "a*b", meaning zero or more 'a's followed by a 'b'.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The Regex engine scans the input string character by character to check the pattern.
• How many times: It goes through the input string once, checking each character in order.

How Execution Grows With Input

As the input string gets longer, the Regex engine spends more time checking each 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 length.

Final Time Complexity

Time Complexity: O(n)

This means the time to check the pattern grows linearly with the size of the input string.

Common Mistake

[X] Wrong: "Regex matching always takes the same time no matter how long the input is."

[OK] Correct: The Regex engine must look at each character to confirm the pattern, so longer input means more work.

Interview Connect

Understanding how Regex time grows helps you write efficient pattern checks and explain your code clearly in real projects or interviews.

Self-Check

"What if the pattern included nested repetitions like (a+)+b? How would the time complexity change?"