Discrete Fourier Transform and FFT

Given the set (Subscript[f, 0]), (Subscript[f, 1]),  (Subscript[f, 2]) ... (Subscript[f, N-1]) of complex numbers, we define the set (Subscript[h, 0]), (Subscript[h, 1]),  (Subscript[h, 2]) ... (Subscript[h, N-1]) so that

and which is called the Discrete Fourier Transform (DFT) for the set (Subscript[f, 0]), (Subscript[f, 1]),  (Subscript[f, 2]) ... (Subscript[f, N-1]). For example, let’s define an arbitrary set of N=100 complex numbers,

ClearAll["Global`*"]
Num=1000;
flist=Table[N[Sin[Sqrt[n]]Sqrt[n+1]-I (n^(1/3))],{n,0,Num-1}];

ListPlot[{Re[flist],Im[flist]}]

According to the above definitions, the list of the DFT numbers is

hnumbers[n_]:=1/Sqrt[Num]Sum[flist[[k+1]]Exp[2Pi I k n/Num],{k,0,Num-1}]

hlist=Table[hnumbers[n],{n,0,Num-1}];

ListPlot[{Re[hlist],Im[hlist]}]

Timing[Table[hnumbers[n],{n,0,Num-1}]][[1]]

Exercise: The Timing command returns the time (in seconds) to evaluate an expression. In the example given, above explore how the time resources vary as a function of the size, Num, of the list.

?Timing

Mathematica's FFT function

In the above exercise you might have noticed how time time resources scale the square power of  Num.
The Fast Fourier Transform algorithm has superior scaling properties, and is implemented by the Mathematica function

?Fourier

FFThlist=Fourier[flist];

ListPlot[{Re[FFThlist],Im[FFThlist]}]

and which agrees with the result obtained above, but whose evaluation time is dramatically improved from the latter.

Timing[Fourier[flist]][[1]]