Pearls of Functional Algorithm Design question
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
Richard sent me a note offlist which quickly cleared up my misconception. I was mistaken that table could contain n^2 elements. A closer reading of the definition of table makes it clear that it will have n elements, so the n log n bound makes perfect sense to me now. Thanks! --Mark P.S. I highly recommend the book.
participants (1)
-
Mark Engelberg