Editing Flex (lexical analyser generator) (section)

=== Time complexity ===
A Flex lexical analyzer usually has time complexity <math>O(n)</math> in the length of the input. That is, it performs a constant number of operations for each input symbol. This constant is quite low: [[GNU Compiler Collection|GCC]] generates 12 instructions for the DFA match loop.{{citation needed|date=November 2015}} Note that the constant is independent of the length of the token, the length of the regular expression and the size of the DFA.

However, using the REJECT macro in a scanner with the potential to match extremely long tokens can cause Flex to generate a scanner with non-linear performance. This feature is optional. In this case, the programmer has explicitly told Flex to "go back and try again" after it has already matched some input. This will cause the DFA to backtrack to find other accept states. The REJECT feature is not enabled by default, and because of its performance implications its use is discouraged in the Flex manual.<ref name=performance>{{cite web |title=Performance - Lexical Analysis With Flex, for Flex 2.5.37 |publisher=Flex.sourceforge.net |date= |url=https://westes.github.io/flex/manual/Performance.html |access-date=2013-02-25}}</ref>