News for hackers. Stuff that matters.
Re:What is the asymptotic cost of purely functional programm... by debacle on Wednesday April 11, 2012 @04:53PM (#3829585)
So it's simply the difference in efficiency between an imperative and a functional algorithm?
Re:What is the asymptotic cost of purely functional programm... by ww520 on Wednesday April 11, 2012 @06:50PM (#3830036)
It is not a matter of imperative or functional. It's the difference between mutable and immutable style programming. You can have an immutable imperative program or a mutable functional program.

Lots of algorithms maintain mutable states. When these algorithms are translated into immutable state style, their complexity (BigO) shoots up. The SO question is asking what's the increased complexity when moving to PURE functional programming style.