Dgdrxrt

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

$B(n) = 5cdot B(fracn3) + 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 + frac53 + (frac53)^2 + ... + (frac53)^k$

Which leads to $3^kcdot (frac103)^k$ -> $5^k = 5^log_3n$ -> $log_3n = k$

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

beginequation
beginsplit
B(n) &= 5B(fracn3) + cn^2 \
&= 5(5B(fracn3^2) + c(fracn3)^2) + cn^2 \
&= 5^2B(fracn3^2) + c[5(fracn3)^2 + n^2] \
&= 5^2(5B(fracn3^3) + c(fracn3^2)^2) + c[5(fracn3)^2 + n^2] \
&= 5^3B(fracn3^3) + c[5^2(fracn3^2)^2 +5(fracn3)^2 + n^2] \
&= vdots \
&= 5^kB(fracn3^k) + c[5^k-1(fracn3^k-1)^2 + ldots +5(fracn3)^2 + n^2]\
&= 5^kB(fracn3^k) + cn^2 sum_i=0^k-1 5^i(frac13^i)^2 \
&= 5^kB(fracn3^k) + cn^2 sum_i=0^k-1 (frac53^2)^i \
&= 5^kB(fracn3^k) + cn^2 frac1-(frac59)^k1- frac59
endsplit
endequation

But $B(1) = c$ hence for $k=log_3 n$
$$B(n) = 5^log_3 nc + frac94 cn^2 (1-(frac59)^log_3 n)$$
It seems that the dominating term is $O(n^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) = cleft(frac454left(frac 95right)^u-1right)
$$

then

$$
B'(u) = C_0 5^u-1 + cleft(frac454left(frac 95right)^u-1right)5^u-1
$$

hence

$$
B(n) = frac120left((4C_0-45c)5^log_3 n+45 c n^2right)
$$

and after incorporating the initial conditions we have

$$
B(n) = frac c4left(9n^2-5^log_3 (3n)right)
$$