The DFT transforms a sequence of \(N\) complex (time-domain) numbers ${x_0, x_1, \ldots, x_{N-1}}$ into a second sequence of complex (frequency-domain) numbers ${X_0, X_1, \ldots, X_{N-1}}$ as shown in the equation below. Because each sample $X_k$ requires \(N\) complex multiplications with the fixed “twiddle factors” $\exp(-i2\pi kn/N)\(, a total of \)N^2$ multiplications are required overall, leading to the computational complexity of \(O(N^2)\).
$$X_k = \sum_{n=0} ^{N-1} x_n \cdot e^{-i\dfrac{2\pi}{N}kn}$$
Direct computation of the above equation can be feasible for cases where \(N\) is not too large. The above equation can be written as a matrix-vector multiplication where the twiddle factors are collected in an $N\times N$ matrix, and the samples $x_n$ are collected in an $N\times 1$ vector. Indeed, a “direct form” solution like this is shown for a Versal DFT design in a following section.