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.