= Divide-and-conquer combination cost
{title2=$T(n)=aT(n/2)+g(n)$}
The combination cost is the work needed to reconstruct an answer from the returned smaller answers. In a <time complexity> calculation, also count partitioning the <input>, preparing arguments, and other work outside <recursive calls>. Write their total as $g(n)$ for a size-$n$ call. For an ideal balanced <divide-and-conquer algorithm> making $a$ calls of size $n/2$, the <recurrence relation> is
$$
T(1)=c_0,\qquad T(n)=aT(n/2)+g(n)\quad(n>1),
$$
where $a$ is a fixed positive <integer> and $c_0>0$ is the <base case> cost. Take $n=2^k$, a <power of two>, so the size becomes one after exactly $k$ divisions. This is a model of total sequential work: all $a$ smaller calls contribute, even if a machine could run some simultaneously.
At level $j$, there are $a^j$ calls, each of size $n/2^j$. Expanding the <recurrence relation> gives the exact identity
$$
T(n)=a^k c_0+\sum_{j=0}^{k-1}a^j g(n/2^j).
$$
The first term counts the <base cases>; the <sum> stops before their level because $g$ describes work in nonterminal calls. This separates depth, number of calls, and local work. <Merge sort> has two smaller calls and a linear <merge algorithm>, giving $T(n)=2T(n/2)+O(n)=O(n\log n)$ in <Big O notation>. The MIT notes derive this by summing equal work across levels, and contrast it with the same two-way split followed by quadratic local work.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 3: Insertion sort, merge sort>[6.006 Introduction to Algorithms, Fall 2011, Lecture 3: slides 32–44, recurrence and equal work per level; slide 46, quadratic local work]{ref}
\Image[/divide-and-conquer-combination-work-levels.png]
{title=The same halving tree can have linear or quadratic work at each call}
{description=Original exact cost models with $n=16$, two children per nonterminal call, and one unit per <base case>. For local work $g(s)=s$, every internal level costs 16 and the total is 80. For $g(s)=s^2$, internal levels cost 256, 128, 64, 32 and the total is 496. The tree shows instance sizes; the ledger counts work rather than execution order.}
For the first constructed model, set $a=2$, $c_0=1$ and $g(s)=s$. Every internal level costs $2^j(n/2^j)=n$, while the leaves cost $n$. Thus $T(n)=n\log_2 n+n$, giving $T(16)=80$. If the same split instead has $g(s)=s^2$, then the <finite geometric series> gives
$$
T(n)=n+n^2\sum_{j=0}^{k-1}2^{-j}=2n^2-n,
$$
so $T(16)=496$. The root alone already costs $n^2$ in this second model. Smaller arguments do not eliminate expensive reconstruction. These are stipulated operation counts, rather than measured running times or exact <merge sort> instruction counts.
<Binary search> has a different saving: after its comparison, only one half remains a candidate. With constant-cost indexed <array> access and comparisons, its worst-case <time complexity> satisfies an upper <recurrence relation> $T(n)\leq T(\lfloor n/2\rfloor)+C$ for $n\geq1$, with $T(0)=c_0$. There is one continuing branch, rather than two. At most $\lfloor\log_2 n\rfloor+1$ nonempty candidate ranges are inspected for $n\geq1$. Copying the retained half into a fresh <array> on every step would add linear work at that step and lose this logarithmic bound. The shrinking range and its representation both matter.
Back to article page
