Theoretical foundations of Divide and Conquer

When it comes to the design of algorithms, one often employs the following techniques:

• Dynamic Programming

• The Greedy-Strategy

• Divide-and-Conquer

While for the first two methods, there are well-known theoretical foundations, namely the Bellman Optimality Principle and matroid (resp. greedoid) theory, I could not find such a general framework for algorithms based on D&C.

Firstly, I am aware of something that we (or rather, the prof) introduced in a functional programming class, called an "algorithmic skeleton", that arose in the context of combinators. As an example hereof, we gave such a skeleton for D&C algorithms as follows:

Definition: Let $A,S$ be non-empty sets. We call the elements of $S$ solutions, and the elements of $P:=\mathfrak{P}(A)$ (that is, the subsets of $A$) are referred to as problems.
Then, a D&C-skeleton is a 4-tuple $(P_\beta, \beta, \mathcal{D}, \mathcal{C})$, where:

• $P_\beta$ is a predicate over the set of problems and we say that a problem $p$ is basic iff $P_\beta(p)$ holds.

• $\beta$ is a mapping $P_\beta \rightarrow S$ that assigns a solution to each basic problem.

• $\mathcal{D}$ is a mapping $P \rightarrow \mathfrak{P}(P)$ that divides each problem into a set of subproblems.

• $\mathcal{C}$ is a mapping $P\times \mathfrak{P}(S) \rightarrow S$ that joins the solutions (depending on kind of a "pivot problem") of the subproblems to produce a solution.

Then, for a given skeleton $s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$ and a problem $p$, the following generic function $f_s: P\rightarrow S$ computes a solution (in the formal sense) for $p$:

$f_s(p)= \left\{
\begin{array}{l l}
\beta(p) & \quad \text{if $p$ is basic}\\
\mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise}
\end{array} \right.$

where in the second line we use the notation $f(X) := \{f(x) : x\in X\}$ for subsets $X$ of the codomain of a mapping $f$.

However, we did not further examine the underlying, "structural" properties of p

A formal treatment (somewhat resembling the model proposed in the question) of the subject using what is called pseudo-morphisms (that is, functions that are almost morphisms, with some pre- and post-computation done), as well as considerations of complexity analysis and parallel implementation of such algorithms are given in:

An algebraic model for divide-and-conquer and its parallelism by Zhijing G. Mou and Paul Hudak
(in The Journal of Supercomputing , Volume 2, Issue 3, pp. 257-278, November 1988)

StackExchange Computer Science Q#14022, answer score: 5