Re: `completion-in-region'

[Lennart Borgman <lennart.borgman@gmail.com>]

On Mon, Apr 12, 2010 at 4:10 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>>> 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.

I do not understand the "for each" here. I thought that since ".*?" is
greedy that means that only the first "a" could match.

But maybe I am missing that the first ".*?" is not anchored. Would
"^.*?a.*?b.*?c" behave differently?

> - 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
>