It's not harder to reason about time complexity with strict evaluation. I think it's a bit harder with lazy evaluation, though. Okasaki uses both strict and lazy evaluation to achieve fast data structures.
"Ironically, pattern matching — one of the most popular features in functional programming languages — is also one of the biggest obstacles to the widespread use of efficient functional data structures. The problem is that pattern matching can only be performed on data structures whose representation is known, yet the basic software-engineering principle of abstraction tells us that the representation of non-trivial data structures should be hidden. The seductive allure of pattern matching leads many functional programmers to abandon sophisticated data structures in favor of simple, known representations such as lists, even when doing so causes an otherwise linear algorithm to explode to quadratic or even exponential time."
Lazy evaluation seriously complicates the cost model, but few languages are lazy.
Going purely functional (Haskell) has its own benefits but also a lot of drawbacks.
If you don't go purely functional, it doesn't make sense to avoid imperative or OO features where they make sense.
In that sense, I think languages which fuse and unify functional and OO approaches are a good strategy. There is a bit of negativity towards them, because they manage to piss off both OO evangelists as well as functional preachers, but that doesn't detract from the technical benefits of such an approach.
The name "pure FP" is a bit of a misnomer, because what people really mean by it is that instead of "side effects" we have "typed effects". The effects always appear in the types of our computations, so they're not really "side" effects anymore, they're a central part of the computation.
I wonder, though, whether there is a tradeoff that is going unmentioned, and I suspect that it is that it makes it more difficult to reason about costs. I feel trapped when I'm writing in a language like Java, but at least the cost model is obvious to me. Am I off base here? Is there some way to develop a similar intuition about costs in an FP language?