= Solution
For fixed $a\geq1$, $b>1$ and $d\geq0$, a version of the <Master theorem> states that, with bounded positive base costs,
$$
T(n)=aT(n/b)+\Theta(n^d),\quad p=\log_ba
\quad\Longrightarrow\quad
T(n)=\begin{cases}
\Theta(n^p),&d<p,\\
\Theta(n^p\log n),&d=p,\\
\Theta(n^d),&d>p.
\end{cases}
$$
Usual floors and ceilings preserve these bounds when a sufficiently large constant-size base case ensures strict size decrease.
* $A$: $T_A(n)=3T_A(\lceil2n/3\rceil)+\Theta(1)$, hence \b[$O(n^{\log_{3/2}3})$], with exponent approximately $2.7095$. Base cases must include $n\leq2$ because the ceiling otherwise need not decrease.
* $B$: $T_B(n)=9T_B(\lceil n/3\rceil)+O(n^2)$, hence \b[$O(n^2\log n)$] by comparison with the equality recurrence having $\Theta(n^2)$ overhead. If that overhead is actually quadratic this is also tight; the stated upper bound alone does not establish a matching lower bound.
* $C$: $T_C(n)=3T_C(n-1)+\Theta(1)$, whose expansion is a <geometric series>, hence \b[$O(3^n)$], in fact $\Theta(3^n)$ for nonzero base costs. The divide-by-a-constant Master theorem does not apply to a decrement by one.
\b[$B$ is asymptotically fastest; $C$ is slowest.] Even the quadratic-logarithmic upper bound for $B$ is smaller than the tight polynomial order of $A$.
Back to article page
