I haven’t actually looked at the code, but the time complexity
should be n log n.

After all, the function in question is torch.fft, where “fft”
stands for “fast Fourier transform,” which uses what you call
the “divide-and-conquer” algorithm and runs in n log n.

It would be false advertising if torch.fft instead used the
sft* algorithm.