What will be the Time Complexity of Regex methods for example in the code given below :

Question

import re

for _ in range(int(input())):

s=input()                                      #input alphanumeric string 

print(sum(map(int,re.findall('\d+',s))))

score 1 · Answer 1 · answered Jul 09 '20 at 13:50

1

This should run in a linear time O(n). Check this questions related to the time complexities of regular expressions

What is the complexity of regular expression?

What's the Time Complexity of Average Regex algorithms?

answered Jul 09 '20 at 13:50

Jagath01234

139
1
10

Fine, but.. OP asked specifically about time complexity of regex implementation _in Python_, and complexity may differ from implementation to implementation. – Reinderien May 10 '22 at 01:35

score 1 · Answer 2 · answered Jul 09 '20 at 13:51

1

The time complexity of findall for this pattern should be O(len(s)) The regex is not backtracking so it should be match-able in linear time. However I do not know the implementation of re, but I would be surprised if it would not match in linear time.

answered Jul 09 '20 at 13:51

Mihai Andrei

1,024
8
11

score 1 · Answer 3 · answered Jul 09 '20 at 14:06

The time complexity is hard to mention as most of the regular expressions are formed on regular languages. Now all the regular languages have their Finite Automata which can either be represented by DFA, NFA or e-NFA. How much time a regex would take would no only be dependent on the size of the pattern to match but also the Finite Automata to compute that regex. It may also be dependent on the actual engine. If it directly constructs the DFA, then each time matching on a input string, is upper bounded by in length(O(n)).

What will be the Time Complexity of Regex methods for example in the code given below :

3 Answers3