Comment on A Regular Expression Matcher (2007)parentComments−user2994cb6yAn FSA matcher will be O(M) - one state transition per input character.−jstimpfle6yIf you're looking at a specific regex (~FSA), then N is constant... If you have a function that runs an arbitrary regex, then N will vary.
Comments
An FSA matcher will be O(M) - one state transition per input character.
If you're looking at a specific regex (~FSA), then N is constant... If you have a function that runs an arbitrary regex, then N will vary.