Hi 성현!
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.
*) “Slow Fourier transform”
Best regards.
K. Frank