On Sun, Apr 07, 2002, Konst Sushenko wrote: > This one helped. Thanks. > > 'reduction' was the key word that made it clear for me. It is not that left >associated (++) reconstructs the list once and again (although one can say that) it >is just that to return the head from the recursive invocations takes quadratic number >of reductions. Right?
I don't think so. I think it only takes linear time to get the head. But once you've gotten the head, it takes linear time again to get the head of the tail, .... You get (I think...) a progression like n+(n-1)+(n-2)+...+1, which is in O(n^2). David _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
