Solving the functional equation $ T (n) = 3 ~ T(\frac{n}{2}) + n^{2} $.

Question

I’m trying to solve the following recurrence relations for run-time $ T(n) $. Assuming $ T(n) $ is constant for $ n \leq 2 $, solve $$ T(n) = 3 ~ T \! \left( \frac{n}{2} \right) + n^{2}. $$

Answer 1

For real $n$ there are exact solutions $A|n|^b + cn^2$ where $A$ is a free parameter and $b,c$ are determined by the recurrence. The recurrence for integer $n$ will approximate that after defining what $T(n/2)$ means.

The exponent $b$ is the same as the fractional dimension of the Sierpinski triangle which is made of $3$ copies of itself at $1/2$ the scale, a form of the same recurrence (without the $n^2$ term).

Answer 2

Since you tagged this asymptotics, note that this fits the form of the Master Theorem, which gives conditions to determine the asymptotic growth of $$T(n) = a T(n/b) + f(n).$$

In this case, $a=3, b=2, f(n)=n^2$ and $\log_2 3 = 1.58$. Thus, by the master theorem, since $2 > 1.58$ and $3\cdot(n/2)^2 = (3/4)\cdot n^2 \leq (3/4) n^2$, we have $T(n) = \Theta(f(n)) = \Theta(n^2)$.

Answer 3

You may notice that by setting $T(n)=4n^2+S(n)$ the original recurrence boils down to something simpler, namely

$$ S(n) =3\cdot S(n/2) $$ admitting the solution $S(n) = n^\alpha$, with $\alpha = \log_2(3)$, such that $$ T(n) = 4n^2 + n^{1.5849625\ldots} $$ is a solution of the original recurrence, that I think may come from the study of Karatsuba's algorithm complexity.

Answer 4

$\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\mrm{T}\pars{n} = 3\,\mrm{T}\pars{n \over 2} + n^{2}:\ ?\,,\qquad \left.\vphantom{\large A}\mrm{T}\pars{n}\right\vert_{\ n\ \leq\ 2} = \mbox{'initial' constant}}$.

Lets $\ds{\,\mrm{T}\pars{n} \equiv \tilde{\mrm{T}}\pars{n}n^{2}\implies \tilde{\mrm{T}}\pars{n} = {3 \over 4}\,\tilde{\mrm{T}}\pars{n \over 2} + 1 \implies\tilde{\mrm{T}}\pars{n} - 4 = {3 \over 4}\bracks{\tilde{\mrm{T}}\pars{n \over 2} - 4}}$ which leads to: \begin{align} \tilde{\mrm{T}}\pars{n} - 4 & = {3 \over 4}\,{3 \over 4}\bracks{\tilde{\mrm{T}}\pars{n \over 2^{2}} - 4} = {3 \over 4}\,{3 \over 4}\,{3 \over 4} \bracks{\tilde{\mrm{T}}\pars{n \over 2^{3}} - 4} = \cdots = \pars{3 \over 4}^{k} \bracks{\tilde{\mrm{T}}\pars{n \over 2^{k}} - 4} \end{align} which is equivalente to $$ \mrm{T}\pars{n} = 4n^{2} + \pars{3 \over 4}^{k}n^{2} \bracks{{\mrm{T}\pars{n/2^{k}} \over \pars{n/2^{k}}^{2}} - 4} $$

---

$$\bbox[8px,#efe,border:0.1em groove navy]{% \mrm{T}\pars{n} = 4n^{2} + \pars{3 \over 4}^{k} \bracks{2^{2k}\,\mrm{T}\pars{n \over 2^{k}} - 4n^{2}}} $$

The final solution is found with a value of $\ds{k}$ which satisfies $\ds{{n \over 2^{k}} \leq 2 \implies k \geq {\ln\pars{n} \over \ln\pars{2}} - 1}$

$$\bbox[8px,#efe,border:0.1em groove navy]{% \mrm{T}\pars{n} = 4n^{2} + \pars{3 \over 4}^{k_{c}} \bracks{2^{2k_{c}}\,\mrm{T}\pars{n \over 2^{k_{c}}} - 4n^{2}}}\,,\qquad \left\{\begin{array}{rcl} \ds{k_{c}} & \ds{\equiv} & \ds{\left\lceil{\ln\pars{n} \over \ln\pars{2}} - 1\right\rceil} \\[2mm] \ds{\mrm{T}\pars{n \over 2^{k_{c}}}} & \ds{=} & \mbox{'initial' constant} \end{array}\right. $$