Regular expression matching (~ operator) in PostgreSQL - Time & Space Complexity

Time Complexity: Regular expression matching (~ operator)

O(n)

Understanding Time Complexity

We want to understand how the time it takes to check if text matches a pattern grows as the text gets longer.

How does the matching process scale when the input text size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM documents
WHERE content ~ '^[A-Z0-9]*$';
    

This query finds all rows where the content column matches a pattern: only uppercase letters and digits.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The regular expression engine checks each character in the content string to see if it fits the pattern.
• How many times: For each row, it scans through the content string characters once, from start to end or until a mismatch is found.

How Execution Grows With Input

As the length of the content string grows, the time to check the pattern grows roughly in proportion to the string length.

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

Pattern observation: The work grows linearly as the string gets longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to match grows in a straight line with the length of the text being checked.

Common Mistake

[X] Wrong: "Regular expression matching always takes the same time no matter how long the text is."

[OK] Correct: The engine usually checks each character, so longer text means more work and more time.

Interview Connect

Understanding how pattern matching time grows helps you write efficient queries and explain performance in real projects.

Self-Check

"What if the regular expression included a wildcard that can match many characters? How would that affect the time complexity?"