Re: What is the runtime complexity of $(filter )?

[Philip Guenther]

On Fri, Jan 8, 2010 at 9:33 AM, Peng Yu <address@hidden> wrote:
> I run $(filter ) with each argument of thousands of strings. It runs
> slow. I'm wondering what the run time complexity of $(filter ) is.
> Suppose I have n strings for each argument. Is the run time complexity
> n*n or log(n)?

It's effectively of complexity O(n).

The proportion of words actually matched affects it slightly, but at
least on my box the effect seems to max out at about 10%.  For
example, when filtering a list of 1,000,000 words, if the filter
matches *none* of them it takes 148 seconds, if it matches *all* of
them it takes 165 seconds.  148/165 = ~90%.


Philip Guenther