[moultano]

>I'm not sure what you mean by "on a small window such that this isn't really applicable"

FFT is very useful on a small window, but algorithms that improve the asymptotic efficiency are unlikely to be useful at that scale. With n=100 the asymptote doesn't matter. We'll still be using the FFT forever, I'm just skeptical that the frontiers of technology will be advanced by a faster FFT, since it seems like the coolest stuff is happening elsewhere. It's increasingly becoming the quick-and-dirty counterpart to the sophisticated-but-slow methods.