[Haskell-cafe] Optimizing spelling correction program

Johan Tibell johan.tibell at gmail.com
Mon Jun 22 07:24:41 EDT 2009


On Mon, Jun 22, 2009 at 12:05 PM, Ketil Malde <ketil at malde.org> wrote:

> Johan Tibell <johan.tibell at gmail.com> writes:
>
> > Typo? Bloom filters have O(1) lookup and tries O(m) lookup where m is the
> > number of characters in the string.
>
> Typically you need to examine the (whole) search string in order to
> compute the hash function, so I think it is fair to consider them both
> O(m).
>

Very true.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090622/200a4a80/attachment.html


More information about the Haskell-Cafe mailing list