[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: `completion-in-region'

From: Stefan Monnier
Subject: Re: `completion-in-region'
Date: Sun, 11 Apr 2010 22:10:50 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux)

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


reply via email to

[Prev in Thread] Current Thread [Next in Thread]