= Solution
The three answers, in source order, are:
* \b[$T(n)=\Theta(n^2)$.] In the <Master theorem>, $a=6$, $b=3$, and $n^2$ grows polynomially faster than $n^{\log_3 6}$. The regularity condition holds because $6(n/3)^2=(2/3)n^2$. For powers of three, expansion even gives $T(n)=3n^2-2n^{\log_3 6}$.
* \b[$T(n)=n^2$, and hence $\Theta(n^2)$.] The <telescoping sum> is $T(n)=1+\sum_{j=2}^n(2j-1)=\sum_{j=1}^n(2j-1)=n^2$.
* \b[$T(n)=\Theta(n^{\log_2 3})$.] Set $m=n-2$ and $U(m)=T(m+2)$. Then $U(m)=3U(m/2)+m+2$, with constant base cost for $m\leq2$. The <Master theorem> with $a=3$, $b=2$ applies because $m+2=\Theta(m)$ is polynomially smaller than $m^{\log_2 3}$. Finally $m=n-2=\Theta(n)$.
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.
Back to article page
