If n is the number of routes, and they are sorted (e.g. implicitly through a prefix tree) and evenly distributed accordingly then then the claim might be plausible by doing log n prefix comparisons of increasingly smaller suffixes of the route to be resolved. I find this line of reasoning unusual and misleading though.
The lower bound is linear in the length of the route if all routes participate in your regular expression and if you have it pre-compiled to, for example, a DFA or an LL parser ahead of time.
k4st|14 years ago
The lower bound is linear in the length of the route if all routes participate in your regular expression and if you have it pre-compiled to, for example, a DFA or an LL parser ahead of time.