Divide-and-conquer algorithms

Suppose you have an algorithm that operates at time-complexity \(O(n^2)\). Then it would be pretty nice if we had a way to reduce a problem with parameter \(n\) into two problems with parameters \(n_1\), \(n_2\) which add up to \(n\). Then we can do the split on each \(n_1\), \(n_2\), and so on and create a tree of some sort.

That sounds like something we could be able to do in various situations, and is known as a divide-and-conquer algorithm.

Below are some examples of divide-and-conquer algorithms:

• *Eigenvalues (QR algorithm) – *In our QR algorithm for the Schur decomposition, in which the matrix is already in upper-Hessenberg form, if at any point some value on the subdiagonal becomes particularly close to zero, we can split the parts of the matrix top-left and bottom-right of it, and perform the algorithm separately on them. This will only reveal the eigenvalues however, and not the full Schur decomposition.
• Fast Fourier transform -- The Discrete Fourier transform can similarly be sped up by dividing the expression into odd and even parts and recognizing that each part is itself a Discrete Fourier transform, then recursively applying this.

I’m aware the articles I’m writing on numerical algorithms aren’t particularly interesting or detailed – I just don’t know of anything interesting to be said about them. If anyone knows something interesting, or any theoretical motivation/“I could have derived this myself” moments, I’d be very interested.