# Time-analysis of the DFT

# 8.1. Time-analysis of the DFT#

As we’ve seen in previous chapters, the naive method for computing the DFT uses two nested loops:

```
1def dft(x):
2 '''Compute the Discrete Fourier Transform of an input signal x of N samples.'''
3
4 N = len(x)
5 X = np.zeros(N, dtype=np.complex)
6
7 # Compute each X[m]
8 for m in range(N):
9
10 # Compute similarity between x and the m'th basis
11 for n in range(N):
12 X[m] = X[m] + x[n] * np.exp(-2j * np.pi * m * n / N)
13
14 return X
```

The outer loop (starting at line 8) iterates over the \(N\) different analysis frequencies: \(m=0, 1, 2, \dots, N-1\).

Within each of these loop is another loop (starting at line 11) that iterates over the *samples* to compute similarity between the input signal \(x\) and the reference complex sinusoid \({e^{-2\pi \cdot \mathrm{j} \cdot m \cdot n / N}}\).
Each step of this inner loop requires a constant amount of work doing basic arithmetic: multiplying, dividing, adding, and storing numbers.
The exact amount of work here isn’t too important: what matters is that it’s the same amount for every choice of \(m\) and \(n\).

Since there are \(N\) steps in the outer loop, and \(N\) steps inside each of those, line 12 is executed \(N^2\) times in total.
This means that as the length of the input grows (i.e., more samples are added), the amount of work grows *quadratically*, as shown below.

This quadratic growth in computation time establishes a baseline for DFT computation: the naive algorithm takes time proportional to \(N^2\). Fast Fourier Transform methods aim to reduce this to scale more favorably as the input length increases.

Coming from the other direction, any algorithm for computing the DFT must take *at least* \(N\) steps, because it must see all \(N\) samples at least once, e.g., to compute \(X[0] = \sum_n x[n]\).
This gives us a lower bound on the computation time, and the goal will be to get as close to this lower bound as possible.