Re: `completion-in-region'

[Stefan Monnier <monnier@iro.umontreal.ca>]

>> If you use ".*?a.*?b.*?c", then yes it gives the
>> same matches but it also has the same O(N^3) worst case.

> This is not the right place perhaps to educate me on this, but to me
> it looks like just three linear searches with the summed length for
> the searches equal to that of the candidate strings. Is not that O(N)?

When matched against "ababab", it will do the following:
- search for a in the string.
- for each match of a, search for b in the remaining string.
- for each match of b, search for c in the remaining string.

These are 3 nested loops, each of them doing a number of iterations
proportional to N, so you get O(N^3) complexity.


        Stefan