Worst case is absurd, yes. But most (all?) added routes that exhibit that behavior are routes that would exhibit that behavior when run as a regex (and hence co

Worst case is absurd, yes. But most (all?) added routes that exhibit that behavior are routes that would exhibit that behavior when run as a regex (and hence converted into a DFA) on their own. (I.e. generally if you would shoot yourself in the foot with this method you've already shot yourself in the foot.) Your worst case is O(nd + O(constructing the new route's DFA)), where "n" is the number of nodes in the previous DFA and "d" is the number of nodes in the DFA of the new route. Note that constructing r's DFA can be done beforehand, and hence the actual time the router will be offline is only O(nd). (Assuming a simple 2 DFA -> 1 NFA -> DFA merge. Your worst case is that every possible pair from the two, and singleton of the two is present in the final DFA, i.e. ({node from old, node from new} -> nd + {node from old} -> n + {node from new} -> d) -> O(nd + n + d) -> O(n*d). Note that this isn't the classic O(2^n) behavior, because we know that, due to the old DFA and new route DFA being DFAs, only one node in n and one node in d can be present at a time in the final stateset. A better bet may be to use the classic "lazily-constructed DFA" approach. In other words, keep it as an NFA while only converting (sets of) nodes to DFA nodes when necessary. If you are worried about memory, you can even do this only for "hot" sections of the NFA, or only for those sections of the NFA that have the most performance gain for the number of nodes added.