How to solve $T(n)=T((4/5)n+1)+n^2$.

Question

I have a problem with this recurrence relation. I have to find the Theta notation. I tried to solve it with the iterative method. The generic formula I calculated is: \begin{equation} T(n)=T[(4/5)^k n]+[(4/5)^{k+1} n]^2+[(4/5)^{k+2} n]^2+\cdots+n^2 \end{equation}

$n=(4/5)^k\Rightarrow k=\log_{4/5}(n)$.

At this point I tried to calculate the geometric series, forgetting the square elevation. I don't know how to continue.

Thanks for your attention.

Answer 1

Hint.

Asymptotically $T(n)\approx T(an)-n^2$ with $a= \frac 45$. Now making $n=a^m$ and substituting we arrive to the equivalent recurrence

$$ R(m) = R(m-1) - \frac{a^{2m}}{a^2} $$

with solution

$$ R(m) = c_0-\frac{a^{2m}-1}{a^2-1} $$

now we can go backwards making $m = \log_a n$, hence $T(n) = \mathcal{O}(n^2)$

Follows a MATHEMATICA script simulating the recurrence (red) as well as the asymptotic approximation (blue)

Clear[Rec, f]
a = 4/5;
f[n_] := (n^2 - 1)/(1 - a^2)
nmin = 5;
nmax = 2000;
Rec[n_] := Module[{}, If[n < nmin, Return[0]];
  If[n == nmin, Return[0]];
  Return[Rec[Floor[a n + 1]] + n^2]
  ]
tab = Table[{n, Rec[n]}, {n, nmin, nmax}];
gr1 = ListPlot[tab, PlotRange -> All, Filling -> Axis, PlotStyle -> {Thick, Red}];
gr2 = Plot[f[x], {x, nmin, nmax}, PlotStyle -> {Blue, Thick}];
Show[gr1, gr2, PlotRange -> All]