That is true of languages, but it is in fact the case that there are algorithms that run in O(n) time when written impurely, but require O(nlogn) or such when w

That is true of languages, but it is in fact the case that there are algorithms that run in O(n) time when written impurely, but require O(nlogn) or such when written in a purely functional style, even in state of the art FP languages. Since FP languages provide impure facilities for use in the real world, you can still use the O(n) algorithms, but at the cost of purity. So the relevant question here really is not "are functional languages inherently slow?", but "is pure functional programming inherently slow?". AFAIK, the answer to that question is not conclusively proven yet.