[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?



More information about the Haskell mailing list