Question bank — Fourier analysis — DFT, FFT algorithm (Cooley-Tukey)

False. The FFT is an exact algorithm for the very same DFT; it only reorganizes the arithmetic. The only difference in practice is floating-point rounding, which is tiny and unrelated to the algorithm's logic.

False. The advantage is $N/{\log }_{2}N$, which grows sublinearly: because the ${\log }_{2}N$ denominator also grows, doubling $N$ gives less than double the speedup (it goes from $N/{\log }_{2}N$ to $2N/({\log }_{2}N+1)$).

True. Conjugate symmetry $X_{N-k}=\overline{X_k}$ makes the upper half the mirror of the lower half, so the $N-1$ nonzero-frequency outputs pair up and only $X_1,\dots ,X_{N/2-1}$ (plus the real $X_0$ and, for even $N$, real $X_{N/2}$) are independent.

False. They are orthogonal but not normal: each has squared norm $N$, not $1$. That leftover factor of $N$ is exactly why the inverse DFT needs a $1/N$.

False. Radix-2 requires $N=2^m$. Arbitrary $N$ needs mixed-radix splitting or Bluestein's algorithm; libraries hide this by padding or switching methods.

False. Beyond $k=N/2$ the indices represent negative frequencies ($k$ stands for $k-N$), so $k=N-1$ corresponds to $-1$ — the lowest-magnitude negative frequency, essentially the slowest wiggle.

False — they define the forward and inverse conventions (a sign flip). Both are valid choices, but you must be consistent: mixing them scrambles the result.

True. $X_k=E_k+{\omega }_N^k{O}_k$ and $X_{k+N/2}=E_k-{\omega }_N^k{O}_k$ (with $E_k,O_k$ the even/odd half-DFTs) reuse the single product ${\omega }_N^k{O}_k$; the compounding of this reuse across levels is the whole source of the speedup.

False. $X_0$ and (for even $N$) $X_{N/2}$ are real, but the others are generally complex — they encode both amplitude and phase.

The flaw is treating $E_k$ as undefined outside its range. $E_k$ (the even-sample half-DFT) is periodic with period $N/2$, so $E_{k+N/2}=E_k$; the butterfly uses this periodicity, it does not violate any domain.

The individual terms are not zero; they are complex numbers of magnitude 1. The sum is zero because it is a geometric series with ratio $r\ne 1$ satisfying $r^N=1$, giving $(r^N-1)/(r-1)=0$.

A real cosine is $\frac{1}{2}(e^{i\theta }+e^{-i\theta })$, so it carries $+3$ and $-3$. The negative frequency $-3$ sits at index $k=N-3$ (since index $k$ means frequency $k-N$), producing two spikes, not one.

We halve the size but there are two subproblems each level, and the $cN$ combine cost recurs at every one of the ${\log }_{2}N$ levels. Summing $cN$ over ${\log }_{2}N$ levels gives $O(N{\log }_{2}N)$, not $O(N)$.

It multiplies your reconstructed signal by $N$, which is a factor of a million for $N=2^{20}$. In any chained pipeline (transform, process, invert) this destroys the numbers and any comparison to the original.

They do not "drop out" — ${\omega }_N^{nk}=1$ means that term contributes $x_n\cdot 1=x_n$ to the sum, it is fully counted, not removed. A weight of 1 is not a weight of 0.

On a discrete grid, frequency $k$ and $k+N$ produce identical samples because $e^{2\pi i(k+N)n/N}=e^{2\pi ikn/N}$. So frequencies wrap modulo $N$, leaving exactly $N$ distinguishable ones.

It lets each coefficient $X_k$ be read off by a single independent projection, so no simultaneous linear system must be solved. Extraction becomes one weighted sum per coefficient.

It turns each even/odd sub-sum $\sum x_{2m}{\omega }_N^{2mk}$ into $\sum x_{2m}{\omega }_{N/2}^{mk}$ — literally a half-size DFT. Recognizing a sub-DFT is what makes the recursion possible.

Because ${\omega }_N^{k+N/2}={\omega }_N^{N/2}{\omega }_N^k=-{\omega }_N^k$ (using ${\omega }_N^{N/2}=-1$): only a sign flips. The expensive product ${\omega }_N^k{O}_k$ is computed once and reused with a minus.

The naïve DFT costs $\sim N^2$ operations (each of $N$ outputs is a sum of $N$ products), while the FFT costs $\sim N{\log }_{2}N$. Their ratio is $N^2/(N{\log }_{2}N)=N/{\log }_{2}N$ — the run-time forms cancel one factor of $N$, leaving the log in the denominator.

Projecting onto a basis vector uses the conjugate inner product, and conjugating $e^{2\pi ikn/N}$ gives $e^{-2\pi ikn/N}={\omega }_N^{nk}$. The inverse, which reconstructs rather than projects, carries the plus sign.

Replacing $k$ by $N-k$ flips the sign of the exponent, and for real $x_n$ that is exactly complex conjugation of the whole sum. Reality of the data becomes a mirror symmetry in the spectrum.

Each level of recursion buys a factor-of-2 saving by computing two outputs per multiply, and there are ${\log }_{2}N$ levels. The savings multiply across levels rather than add.

Just the sample itself: $X_0=x_0$. This is the recursion's base case — a length-1 "DFT" is the identity, which is where FFT recursion bottoms out.

The plain sum ${\sum }_{n=0}^{N-1}{x}_n$, since ${\omega }_N^0=1$ for every term. It is the DC component — $N$ times the average of the signal.

${\omega }_N^{N/2}=e^{-i\pi }=-1$, so $X_{N/2}={\sum }_n{x}_n(-1{)}^n$ — a purely alternating sum. For real input this coefficient is real; it is the Nyquist frequency (see Sampling & Aliasing (Nyquist)).

Radix-2 splitting stalls — you cannot cleanly halve. You must switch to mixed-radix, pad to the next power of two, or use Bluestein, otherwise the even/odd trick doesn't apply.

Only $X_0=Nc$ is nonzero; every other $X_k=0$ because ${\sum }_n{\omega }_N^{nk}=0$ for $k\ne 0$ (that vanishing geometric series again). A constant signal is pure DC.

Every $X_k=1$: the weighted sum picks out only the $n=0$ term, whose weight ${\omega }_N^0=1$ for all $k$. A spike in time is a flat, all-frequencies spectrum — the discrete uncertainty principle in miniature.