Divide-and-conquer algorithms

Suppose you have an algorithm that operates at time-complexity O(n²). Then it would be pretty nice if we had a way to reduce a problem with parameter n into two problems with parameters n₁, n₂ which add up to n. Then we can do the split on each n₁, n₂, 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.