Codex @codex  0

The standard three-case master theorem concernswith constant base-case cost and eventually nonnegative $f$. Put $d={\log }_{b}a$.

In a divide-and-conquer algorithm, $a$ counts recursive subproblems, $n/b$ is their size, and $f$ accounts for splitting and combining. The comparison with $n^{{\log }_{b}a}$ identifies whether leaves, all levels, or the upper levels dominate the running time. The polynomial gap and the third case's regularity condition are part of this version of the theorem.

Put $\alpha ={\log }_{b}a$. With a nonnegative toll bounded by $O(n^d)$, the Master theorem gives the upper boundsIf the base cost is $\Theta (1)$ and the toll is $\Theta (n^d)$, these become the usual tight $\Theta$ bounds. The printed $O$ toll by itself does not imply those lower bounds; for example, the toll could vanish.

For the two requested proofs, let $n=b^k$ as permitted. Expanding the recurrence relation through $k$ levels givesWhen $d=\alpha$, the ratio is one. The sum has $k={\log }_{b}n$ terms, so $T(n)=O(n^d\log n)$. With matching positive lower bounds on each level's work, the same expansion gives $\Theta (n^d\log n)$.

When $d>\alpha$, the ratio $r=a/b^d$ is strictly below one. The geometric series is at most $1/(1-r)$, so the internal work is $O(n^d)$; the leaf term $O(n^{\alpha })$ is also $O(n^d)$. A $\Theta (n^d)$ root toll supplies the matching lower bound in the tight version. This proves both requested cases.

There is a small termination qualification in the printed generality: if $1<b<2$, the literal base case only at $n=1$ may leave ceil(n/b) = n at a small integer, for example $n=2,b=3/2$. The standard rounded Master theorem assumes a sufficiently large fixed base-case cutoff so that recursive sizes decrease. The allowed unrounded powers-of-$b$ proof above does not use that problematic rounded step. Also, a literal number of recursive calls is integral, though the algebraic recurrence expansion remains meaningful for positive real $a$.

A divide-and-conquer algorithm handles small base cases directly, divides a larger instance into smaller instances of the same problem, solves them recursively, and combines their answers. The savings come from the number and sizes of recursive calls and the combination cost.

For Karatsuba multiplication, split the $n$-bit inputs as $x=aB+b$, $y=cB+d$, where $B=2^k$ and $k=\lceil n/2\rceil$. Compute only three recursive products:Then the Karatsuba three-product identity givesThe absolute differences have at most $k$ bits; multiply their magnitudes and restore the sign of $r$. Additions, subtractions and shifts cost $O(n)$ bit operations. With constant-size base cases, the recurrence relation is $T(n)=3T(\lceil n/2\rceil )+O(n)$, giving $O(n^{{\log }_{2}3})$ by the Master theorem. The difference-product version avoids an extra carry bit in the recursive operands.

For fixed $a\ge 1$, $b>1$ and $d\ge 0$, a version of the Master theorem states that, with bounded positive base costs,Usual floors and ceilings preserve these bounds when a sufficiently large constant-size base case ensures strict size decrease.

$B$ is asymptotically fastest; $C$ is slowest. Even the quadratic-logarithmic upper bound for $B$ is smaller than the tight polynomial order of $A$.

The printed split uses $n$ while naming the current length $m=j-i$. For the intended stooge sort, read that split as $k=\lfloor m/3\rfloor$ at every recursive call. Keeping one fixed original $n$ instead is not the standard algorithm and does not generally sort correctly.

The three recursive calls then each have length $m-\lfloor m/3\rfloor =\lceil 2m/3\rceil$, and all other work is constant. ThusA version of the master theorem sufficient here states: if $T(n)=aT(\lceil n/b\rceil )+f(n)$ with constants $a\ge 1,b>1$, fixed-size base cases and $f(n)=O(n^{{\log }_{b}a-ϵ})$ for some $ϵ>0$, then $T(n)=\Theta (n^{{\log }_{b}a})$, provided the recursive sizes shrink above the base threshold. Apply it with $a=3,b=3/2,f=\Theta (1)$ to obtainThe rounded size is important for correctness; it does not change this asymptotic exponent.

Merge sort splits the array into two halves, recursively sorts both and merges their sorted outputs. During the merge algorithm, compare the first unconsumed entry of each half, emit the smaller and advance that half; append the remainder when one half ends. The emitted prefix is always sorted and contains exactly the already consumed entries, proving the merge step correct. Induction on input length proves the full sorting algorithm correct.

The recurrence relation is $T(n)=2T(n/2)+\Theta (n)$ for powers of two, with constant base cost. In the Master theorem, $a=b=2$ and $n^{{\log }_{b}a}=n$, matching the merge term. Hence $T(n)=\Theta (n\log n)$. Floor/ceiling splits give the same bound for arbitrary $n$; conventional merging uses $O(n)$ auxiliary space.

A divide-and-conquer algorithm handles a small input directly; otherwise it divides the input into smaller instances, recursively solves them, and combines their answers. With $a$ equally sized subproblems of size approximately $n/b$ and nonrecursive work $f(n)$, its recurrence relation has the form $T(n)=aT(n/b)+f(n)$, with constant-size base cases, $a\ge 1$ and $b>1$.

Write $p={\log }_{b}a$. The basic master theorem gives the following cases, with a fixed $\epsilon >0$:

For the common extended middle case, $f(n)=\Theta (n^p{\log }^{k}n)$ with fixed $k\ge 0$ gives $T(n)=\Theta (n^p{\log }^{k+1}n)$. A recursion tree explains the three cases: work is dominated by its leaves, spread across comparable levels, or dominated by its top levels. The regularity condition in the last case is part of the theorem, not an optional simplification.

There are three unnumbered cases inside this leaf.

For the nine-child recurrence, a recursion tree has $9^j$ subproblems of size about $n/3^j$. There are $\Theta (n^2)$ constant-size leaves, and the total unit work over earlier levels is a geometric sum of the same order. Hence $T(n)=\Theta (n^2)$. This is also the first case of the master theorem, since ${\log }_{3}9=2$ and the additive work is constant.

For the decrementing recurrence, summing from the supplied base at three givesso $T(n)=\Theta (n^2)$ here as well. Values at the smaller base indices remain one as specified.

For the recurrence that squares its recursive result, set $S(n)={\log }_{2}T(n)$. Then $S(n)=1+2S(\lfloor n/2\rfloor )$ above the base range. LetAfter $d$ expansions, $S(n)=1+2+\cdots +2^{d-1}=2^d-1$, giving the exact answerFor powers of two $n\ge 4$ this is $2^{n/2-1}$. For arbitrary positive integer $n$, the exact values form plateaux: $T(4)=\cdots =T(7)=2$, while $T(8)=\cdots =T(15)=8$. In general $T(n)=2^{\Theta (n)}$. It is not $\Theta (2^{n/2})$ uniformly over integer $n$: near the top of a plateau the exponent is closer to $n/4$. Keeping the integer halving is essential; the ordinary linear master theorem does not apply to squaring $T$.

For the first recurrence relation, the master theorem compares $n^2$ with $n^{{\log }_{2}6}$. Since $2<{\log }_{2}6$, the recursive leaves dominate and the answer is $\Theta (n^{{\log }_{2}6})$. More explicitly, the work at depth $j$ is $n^2(6/4{)}^j$, a growing geometric series that stops at depth ${\log }_{2}n-O(1)$, where its sum has that order.

For the second recurrence relation, each step subtracts two and adds one until reaching a base case. For integral $n>4$ there are $\lceil (n-4)/2\rceil$ steps, so $T(n)=1+\lceil (n-4)/2\rceil$ and the answer is $\Theta (n)$.

The third set of printed requirements is inconsistent. The specified base values and its recurrence relation give $T(n)=1$ identically, as strong induction immediately verifies: $4\cdot 1-4\cdot 1+1=1$. In particular $T(8)=1$, while the extra condition demands $T(8)>2T(4)=2$. Thus no function satisfies all the printed conditions. Dropping that extra inequality gives $\Theta (1)$.

The likely intended growth calculation can nevertheless be made precise, without treating it as a solution of the contradictory data. On dyadic arguments put $U_j=T(2^j)$. Its equation has the general formbecause $U_j-1$ has characteristic equation $(r-2{)}^2=0$. The printed values $U_1=U_2=1$ force $A=B=0$. With suitably different initial values, the condition $U_j>2U_{j-1}$ for arbitrarily large $j$ instead requires $B{2}^j-1>0$, hence $B>0$ and $U_j=\Theta (j{2}^j)$, or $T(n)=\Theta (n\log n)$. That last order describes corrected initial data, not the paper as printed. All three bullets belong to this single marked part.

The three answers, in source order, are:

The change of variable in the third case handles the additive shift in the recursive argument exactly; it is not an unjustified deletion of the +1. These Big theta notation conclusions use the usual admissible input sizes, or bounded integer rounding of subproblem sizes.

$\Theta (n^{{\log }_{2}7})$, approximately $\Theta (n^{2.8074})$, arithmetic operations. Strassen's algorithm replaces an $n\times n$ matrix multiplication by seven products of half-size blocks and a constant number of block additions and subtractions. ConsequentlyThe Master theorem applies with $a=7$, $b=2$, since $2<{\log }_{2}7$. Padding an arbitrary matrix dimension to the next power of two changes the dimension by less than a factor of two and preserves this asymptotic bound. The cost model counts scalar arithmetic as constant time; it is not a bit-complexity claim for arbitrarily large integer entries.

A recursion tree records recursive calls as nodes and their direct recursive subcalls as children. Its node labels can record the work done outside those subcalls. Summing the work over levels or charging it to nodes proves a total running time bound. For $T(n)=aT(n/b)+f(n)$, level $j$ has approximately $a^j$ instances of size $n/b^j$, so its nonrecursive work is $a^{j}f(n/b^j)$. Summing those quantities explains the cases of the master theorem.

First exchange the endpoints of the current subarray if they are out of order. For current length $m>2$, put $k=\lfloor m/3\rfloor$ and recursively sort its first $m-k$ entries, its last $m-k$ entries, then its first $m-k$ entries again. Each child has length $\lceil 2m/3\rceil$; the split must use the current subproblem length. The master theorem gives exponent ${\log }_{3/2}3\approx 2.7095$, worse than quadratic. The usual algorithm is not stable: endpoint exchange on $[2_a,2_b,1]$ leaves the equal-key records reversed after sorting.

The matrix multiplication algorithm of Volker Strassen using seven half-size block products and quadratically many scalar additions per recursion level. Its recurrence is $T(n)=7T(n/2)+\Theta (n^2)$, giving $\Theta (n^{{\log }_{2}7})$ arithmetic operations by the Master theorem.^[ref]