Question

What is the cost of computation of FFT? (Note: ‘N’ is the number of grid points).

(a) N

(b) log ⁡N

(c) N log ⁡N

(d) \(\frac{N^2}{2} \)

I have been asked this question during an internship interview.

This interesting question is from Finite Difference Methods topic in chapter Finite Difference Methods of Computational Fluid Dynamics

Answer 1

The correct choice is (c) N log ⁡N

To explain I would say: The cost of computation is reduced by FFT. FFT has a cost of computation of N  log⁡ N orders. This is much lower than N^2, especially when N is large. This reduces the problem of computation cost in the Spectral method.