[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: What is the runtime complexity of $(filter )?

**From**: |
Philip Guenther |

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

**Date**: |
Fri, 8 Jan 2010 10:29:18 -0800 |

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