 To verify the correctness of an FFT implementation, rigorous guarantees can be obtained in O("N" log "N") time by a simple procedure checking the linearity, impulse-response, and time-shift properties of the transform on random inputs (Ergün, 1995).As defined in the multidimensional DFT article, the multidimensional DFT

transforms an array "x"n with a "d"-dimensional vector of indices formula_26 by a set of "d" nested summations (over formula_27 for each "j"), where the division n/N, defined as formula_28, is performed element-wise.Equivalently, it is the composition of a sequence of "d" sets of one-dimensional DFTs, performed along one dimension at a time (in any order).