Lower complexity bounds without mutation
See the section labelled "Negative result: you cannot avoid some slowdown, for some data structures" of https://cs.stackexchange.com/a/18266/755 for examples of problems whose solution in a functional language is inherently a bit slower than a solution in an imperative language with mutation.  One example is an array data structure; with mutation, you can achieve $O(1)$ worst-case time for both mutation and lookup, but with a functional language (with persistent data structures), you cannot.