### Logarithmic Slowdown of Functional Languages?

The Wikipedia page on "Functional Programming" has some assertions about efficiency that sound questionable. I'm not the only one--someone else tagged the item with "citation needed" and started a discussion.

It currently says, "Any imperative algorithm is expressible in these languages with a logarithmic slowdown in the worst case." David Hopwood notes in the discussion that "Imperative algorithms are expressible with no asympotic slowdown," using some clever/complicated technique involving mutable arrays (citing a caml-list posting by one Tom Breuel).

All of this sounds a bit strange to me--as far as I know, there's no conclusive reason to think that functional languages must execute a particular algorithm more slowly than an imperative language. (Where does this "logarithmic slowdown" come from, anyway?) But I don't have a mastery of all the relevant literature. Can someone else jump in and straighten this out?

## Comments

The logarithmic slowdown is from having to use immutable data structures, e.g. balanced trees for associative lookup instead of hash tables. There is a theorem saying the slowdown is unavoidable under some assumptions. Haskell gets around it with some mutable types enclosed in monads.

Posted by: asdf | February 27, 2008 7:41 AM

The logarithmic slowdown is from having to use immutable data structures, e.g. balanced trees for associative lookup instead of hash tables. There is a theorem saying the slowdown is unavoidable under some assumptions. Haskell gets around it with some mutable types enclosed in monads.

Posted by: asdf | February 27, 2008 7:42 AM

I don't see why that should lead to a logarithmic slowdown as such. It could be that you happen to have a data-structure whose depth is logarithmic in its total size (such as a balanced tree) and in that case updating a small piece of it would cause logarithmically-many operations in the worst case (re-creating the spine of the structure). But that's not a general "logarithmic slowdown" for functional languages, its a set of particular situations. The real outcome could be better or worse than that.

I'd like to see this theorem you mention.

Posted by: Ezra | September 10, 2008 12:59 PM