A sample code, where I try to verify if the string is a valid interger
public static boolean isValidNumberUsingRegex(String num) { return num.matches("[-+]?\\d+(\\.\\d+)?"); } What is the time complexity of matches ?
2 Answers
That depends on the implementation of the regex engine. Assuming that nothing really awkward happens (there should be no backtracking involed in this regexp for example), I would say that the DFA resulting from your expression would accept/reject any string in O(n).
Here's a depiction of the expression from Regexper:
Note that there's no way to say what the complexity is for a general regexp. Some regexps require backtracking and you can craft expressions which take exponential time to match. So my answer applies to this particular expression, and this particular expression (any particular expression actually) is compiled into a DFA in O(1).
Comments
Typically in a regex implementation a DFA is constructed when you construct the pattern, and then that DFA is used to match against the given string.
If you keep the method as it is, it is probably consistently going to be near O(n*m), where n is the length of the pattern and m is the length of the string, because the DFA will need to be constructed each time. On the other hand, if you use the Pattern class to precompile a DFA, then you can achieve much better results.
In terms of the complexity once you have a pattern pre compiled, you should approach the following complexity:
On matches, it will take at least O(m) time, where m is the length of the string
On mismatches (not a number), you can achieve anywhere between O(1) and O(m-1) time depending on where the pattern falls off the DFA.
If you are interested in how the DFA is created I suggest you watch this video. I found it helpful when learning:
2 Comments
dhalik
Well since the function can take any string to match against, it is not constant... right?
aioobe
The question is not about the complexity of String.matches for a general regexp, but the complexity of String.match with the posted regexp. The posted regexp has a fixed length, i.e. m is constant.
O(n)wherenis the length of the string. think of a DFA