Recurrence Relation: $B(n) = 5\cdot B(n/3) + c(n^2)$

Question

I'm working on deriving this recurrence relation in the form $O(n^d)$ for some value of d:

$B(n) = 5\cdot B(\frac{n}{3}) + cn^2$

The initial condition is:

$B(1) = c$

I'm having trouble incorporating the n^2 into my derivation. This is what I have so far:

We set $n = 3^k$

$5^k(1 + \frac{5}{3} + (\frac{5}{3})^2 + ... + (\frac{5}{3})^k$

Which leads to $3^k\cdot (\frac{10}{3})^k$ -> $5^k = 5^{log_3n}$ -> $log_{3}n = k$

Not sure how to derive the final running time to be $O(n^d)$. Any help would be appreciated!

Answer 1

\begin{equation} \begin{split} B(n) &= 5B(\frac{n}{3}) + cn^2 \\ &= 5(5B(\frac{n}{3^2}) + c(\frac{n}{3})^2) + cn^2 \\ &= 5^2B(\frac{n}{3^2}) + c[5(\frac{n}{3})^2 + n^2] \\ &= 5^2(5B(\frac{n}{3^3}) + c(\frac{n}{3^2})^2) + c[5(\frac{n}{3})^2 + n^2] \\ &= 5^3B(\frac{n}{3^3}) + c[5^2(\frac{n}{3^2})^2 +5(\frac{n}{3})^2 + n^2] \\ &= \vdots \\ &= 5^kB(\frac{n}{3^k}) + c[5^{k-1}(\frac{n}{3^{k-1}})^2 + \ldots +5(\frac{n}{3})^2 + n^2]\\ &= 5^kB(\frac{n}{3^k}) + cn^2 \sum_{i=0}^{k-1} 5^i(\frac{1}{3^i})^2 \\ &= 5^kB(\frac{n}{3^k}) + cn^2 \sum_{i=0}^{k-1} (\frac{5}{3^2})^i \\ &= 5^kB(\frac{n}{3^k}) + cn^2 \frac{1-(\frac{5}{9})^k}{1- \frac{5}{9}} \end{split} \end{equation}

But $B(1) = c$ hence for $k=\log_3 n$ $$B(n) = 5^{\log_3 n}c + \frac{9}{4} cn^2 (1-(\frac{5}{9})^{\log_3 n})$$ It seems that the dominating term is $O(n^2)$.

Answer 2

$$ B(3^{\log_3 n})-5B(3^{\log_3 \frac n3})=c n^2 $$

now calling $B'(u) = B(3^u)$ with $u = \log_3 n$ we have

$$ B'(u)-5B'(u-1) = c 9^u $$

this is a linear recurrence with solution

$$ B'(u) = B'(u)_h + B'_p(u)\\ B'_h(u)-5B'_h(u-1) = 0\\ B'_p(u)-5B'_p(u-1) = c 9^u $$

with $B'_h(u) = C_0 5^{u-1}$ Now making $B'_p(u) = C_0(u)5^{u-1}$ and substituting into the particular we get the recurrence

$$ C_0(u)-C_0(u-1) = c 9^u5^{u-1} $$

with solution

$$ C_0(u) = c\left(\frac{45}{4}\left(\frac 95\right)^u-1\right) $$

then

$$ B'(u) = C_0 5^{u-1} + c\left(\frac{45}{4}\left(\frac 95\right)^u-1\right)5^{u-1} $$

hence

$$ B(n) = \frac{1}{20}\left((4C_0-45c)5^{\log_3 n}+45 c n^2\right) $$

and after incorporating the initial conditions we have

$$ B(n) = \frac c4\left(9n^2-5^{\log_3 (3n)}\right) $$