[femto]

The other observation I make is that apart from their computational complexity, FFTs work well in hardware because they have reasonably efficient implementations.

Implementation of an FFT on a chip has two components: the logic/computing elements ( governed by O(n.log(n)) ) and the routing of signals between those elements. It turns out the size and speed of the FFT is mainly determined by the routing, not by the logic, and there is a tractable routing solution to a reasonable number of points [1]. The computation complexity becomes secondary if the complexity of the implementation is determined by the non-computational aspects.

[1] Based on experience in 1995.