[Haskell] Pearls of Functional Algorithm Design question
Mark Engelberg
mark.engelberg at gmail.com
Mon Jan 3 00:40:32 CET 2011
I'm currently reading the excellent Haskell-based book "Pearls of
Functional Algorithm Design". I have a question about Chapter 2, the
"surpassing problem".
According to the book, "since join takes linear time, table is
computer in O(n log n) steps".
However, as far as I can tell, join takes linear time proportional to
the number of elements in *table*, and the number of elements in table
is potentially as large as n^2 where n is the length of the original
list. So it seems like a quadratic algorithm or worse, to me. What
am I missing?
Thanks,
Mark
More information about the Haskell
mailing list