As mentioned in the DiscreteTransforms[FourierTransform] help page, the efficiency of computing the input transform using the fast methods (mintime and minstorage) is greatly enhanced if the data length for the transform is highly composite (that is, splits into small prime factors).

A (very) rough approximation of the expense of the FFT algorithms when used with $N$ data points, and having a prime factorization of $N=N_1{N}_2\mathrm{...}{N}_m$ with all $N_i<N_{i+1}$ is that the expense is proportional to  $N\cdot N_m\cdot \frac{\log \left(N\right)}{\log \left(N_m\right)}$. The DFT (discrete Fourier transform) algorithm simply has an expense of $N^2$. (For additional information on the algorithm=DFT option, see DiscreteTransforms[FourierTransform].)

The expense of FFT algorithms is highly dependent on the factorization of the data length while the expense of the DFT algorithm is not. If $N$ is prime, the expense of both algorithms is approximately the same.

The best case performance for the FFT algorithms can be observed when the data length is a power of 2. In this case the FFT expense is proportional to $N\log \left(N\right)$, which compares to an expense of $N^2$ for the DFT algorithm. A very significant factor of improvement.

The FourierTransform and InverseFourierTransform commands provide the padding option for padding the input data with zeros to obtain a better data length, but this is not always desirable, as it distorts the high frequency portion of the transform (hence, it is provided as an option).

In addition to time efficiency, storage space can also be a concern when dealing with large data Arrays. The primary consideration here is that the input data should be provided in the form of a single Array (or Vector or Matrix) with $\mathrm{datatype}={\mathrm{complex}}_8$, as this is the datatype used in the implementation of the algorithms, and inplace=true should be specified. If a different datatype is used (for example, two ${\mathrm{float}}_8$ Arrays, or a single complex Array), the input is converted to ${\mathrm{complex}}_8$ datatype, which effectively doubles the required storage for the input data alone.

For a composite data length, the minstorage FFT algorithm requires the least additional storage to compute the Fourier transform. Assuming the work is being done in-place (via inplace=true), in addition to the input data (which is also the output data) it requires additional complex storage of twice the size of the largest prime in the data length.

In contrast (again for a composite data length) the mintime algorithm requires additional complex storage that is equal to the maximum size of any single transform being computed (for a single 1-D transform this is simply the data length) or twice the size of the largest prime in the data length, whichever is larger.

This can become very significant for large data sets.

Note: In general, the run time of the mintime algorithm is always better or equal to the run time of the minstorage algorithm.

For a prime data length, the DFT algorithm requires the least additional storage, needing only 1.5 times the size of the input data length (which is 25% less than the mintime and minstorage algorithm if the data length is prime). But if a transform is of prime length, and sufficiently large so that the memory usage becomes an issue, it would take a very long time to compute the DFT.

As a final note for economy of space, if padding is to be used, but space is a concern, then the padding should be done manually by allocating the data array to be the desired padded size, and populating only the first entries with data values, setting all remaining entries to zero (that is, doing the padding manually).

$\mathrm{with}\left(\mathrm{DiscreteTransforms}\right)$

$\left[\mathrm{DiscreteWaveletTransform}\&comma;\mathrm{FourierTransform}\&comma;\mathrm{InverseDiscreteWaveletTransform}\&comma;\mathrm{InverseFourierTransform}\&comma;\mathrm{WaveletCoefficients}\&comma;\mathrm{WaveletPlot}\right]$

$\mathrm{Digits}≔15\&colon;$

$N≔1000000\&colon;$

$Z≔\mathrm{Vector}\left(N\&comma;\mathrm{datatype}=\mathrm{complex}\left[8\right]\right)\&colon;$

$\mathrm{Za}≔\mathrm{ArrayTools}:-\mathrm{ComplexAsFloat}\left(Z\right)\&colon;$

fill := proc(N,Za) local i;
    for i to N do
        Za[2*i-1] := sqrt(i/N);
        Za[2*i] := sin(10*i/N);
    end do:
end proc:

$\mathrm{evalhf}\left(\mathrm{fill}\left(N\&comma;\mathrm{var}\left(\mathrm{Za}\right)\right)\right)\&colon;$

$\mathrm{tt}≔\mathrm{time}\left(\right)\&colon;$

$\mathrm{FourierTransform}\left(Z\&comma;\mathrm{inplace}=\mathrm{true}\&comma;\mathrm{algorithm}=\mathrm{minstorage}\right)\&colon;$

$\mathrm{time}\left(\right)-\mathrm{tt}$

$0.151$

$\mathrm{evalhf}\left(\mathrm{fill}\left(N\&comma;\mathrm{var}\left(\mathrm{Za}\right)\right)\right)\&colon;$

$\mathrm{tt}≔\mathrm{time}\left(\right)\&colon;$

$\mathrm{FourierTransform}\left(Z\&comma;\mathrm{inplace}=\mathrm{true}\&comma;\mathrm{algorithm}=\mathrm{mintime}\right)\&colon;$

$\mathrm{time}\left(\right)-\mathrm{tt}$

$0.126$