Notes on algorithms and complexity. Divide-and-conquer

Chapter 2. Divide-and-Conquer Algorithms

Recurrence relations

Master theorem:

$$T(n)=a T(\lceil n / b\rceil)+O\left(n^{d}\right)$$

for some constants (a>0) , (b>1) ,and (d ≥0) , then

$$T(n)= \begin{cases}O\left(n^{d}\right) & if d>log _{b} a \\ O\left(n^{d} log n\right) & if d=log _{b} a \\ O\left(n^{log _{b} a}\right) & if d<log _{b} a .\end{cases}$$

d is the exponent of the time complexity of the non-recursive part (i.e., the work done outside each recursive call).

Example: the divide-and-conquer algorithm for integer multiplication

$$T(n)=3 T(n / 2)+O\left(n\right)$$

FFT

Basic idea: use divide-and-conquer to bring the complexity of the polynomial multiplication algorithm down to O(n logn)

Concrete implementation: borrowing the point-value representation of polynomials (n+1 points determine a degree-n polynomial), multiplication can be done in O(n), so convert the polynomial multiplication into a multiplication in the point-value representation and then convert back to the original coefficient representation

The FFT formula:

$$\begin{aligned} \begin{bmatrix} y_0 \\ y_1 \\ y_2 \\ \vdots \\ y_{n-1} \end{bmatrix} &= \begin{bmatrix} W_n^{0\cdot0} & W_n^{0\cdot1} & W_n^{0\cdot2} & \cdots & W_n^{0\cdot(n-1)} \\ W_n^{1\cdot0} & W_n^{1\cdot1} & W_n^{1\cdot2} & \cdots & W_n^{1\cdot(n-1)} \\ W_n^{2\cdot0} & W_n^{2\cdot1} & W_n^{2\cdot2} & \cdots & W_n^{2\cdot(n-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ W_n^{(n-1)\cdot0} & W_n^{(n-1)\cdot1} & W_n^{(n-1)\cdot2} & \cdots & W_n^{(n-1)\cdot(n-1)} \end{bmatrix} \begin{bmatrix} x_0 \\ x_1 \\ x_2 \\ \vdots \\ x_{n-1} \end{bmatrix} \end{aligned}$$

We design the fast Fourier transform (FFT), which converts coefficients to values in time, where the points are the complex (n)-th roots of unity:

$$(1, \omega, \omega^2, \dots, \omega^{n-1}).$$

That is:

$$\langle \text{value} \rangle = \text{FFT}(\langle \text{coefficients} \rangle, \omega).$$ $$\langle \text{coefficients} \rangle = \frac{1}{n} \text{FFT}(\langle \text{values} \rangle, \omega^{-1}).$$

The fast Fourier transform (FFT) multiplies an arbitrary (n)-dimensional vector (i.e., the coefficient representation) by the (n \times n) matrix:

$$M_n(\omega) = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega & \omega^2 & \cdots & \omega^{n-1} \\ 1 & \omega^j & \omega^{2j} & \cdots & \omega^{(n-1)j} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \cdots & \omega^{(n-1)(n-1)} \end{bmatrix}.$$

The (j, k)-th entry of the matrix (counting from zero) is .

Inverse formula:

$$M_n(\omega)^{-1} = \frac{1}{n} M_n(\omega^{-1}).$$

A detailed explanation of the fast Fourier transform

---

Translated from the Chinese original.