Recurrence $T(n) = T({2n\over5}) +n$ using Master Theorem

Question

Solve the recurrence $$T(n) = T\left({2n\over5}\right) +n$$

---

My attempt:

$a=1$,$\ b=\frac 52$, $f(n)=n$

For the most part I believe that is correct. Now I was wondering if my math is correct in this next step. $n^{\log_b a}$ if $a=1$ and $b=\frac 52$ then:

$n^{\log_b a} = n^{\log_{5/2} 1} = n^0 = 1$ (Let me know if this is incorrect)

$f(n) \ \ \ \ \text{vs.} \ \ \ \ n^{\log_b a} \\ \ \ \ n \ \ \ \ \ \ \text{vs.} \ \ \ \ \ \ \ 1$

Assuming $n\ge 1$ this is case 3.

$n = \mathcal O(n^{1+\epsilon}) \quad \text{ for }\epsilon = ? $

Does/can epsilon equal $0$?

I can figure out the regularity condition, I just want to make sure these steps are correct, before I move on.

Answer 1

You want to know if $T(n)$ is comparable to $n$. Just try the obvious, $T(n) \sim Cn$ and find $C$:

$Cn = \frac{2}{5}Cn + n$, so that $C = \frac{5}{3}$ and in fact this solves the recurrence.

$ T(n)= 5n/3$ is a particular solution (for the smoothed recurrence that allows rational $n$ as arguments instead of rounding $2n/5$)

and $E(n) = T(n) - 5n/3$ satisfies

$E(n) = E(2n/5)$ which for rational-$n$ solutions bounded near $0$ would mean $T(n) = 5n/3 + O(1)$.

If you really meant the unsmoothed, integer recurrence, the recurrences for $T$ and $E$ are solved up to bounded error $O(1)$ and compute the value at $n$ in $O(\log n)$ steps that add up those errors, so the result will be

$T(n)=\frac{5n}{3} + O(\log n)$.

Answer 2

Assuming $n\ge 1$ this is case 3.

$n = \Omega(n^{1+\epsilon}) \ \ \ \ \ \ for \ \epsilon = ??$

Does/can epsilon equal $0$?

What are you referring to? Case 3 applies and yields directly $T(n)=\Theta(n)$.

As a confirmation, one can check that the property $T(n)\leqslant2n+c$ is hereditary for every $c$, hence is true for $c$ large enough. In the other direction, $T(n)\geqslant n$ hence indeed, $T(n)=\Theta(n)$.

Answer 3

$$T(n) = n + T(\frac{2n}{5}) = n + (\frac{2}{5}n + T(\left(\frac{2}{5}\right)^2 n) = \cdots = n+ \frac{2}{5}n + \left(\frac{2}{5} \right)^2n + \left(\frac{2}{5} \right)^3n + \cdots$$ and therefore $$T(n) \leq \frac{1}{1-\frac{2}{5}}n + c = \frac{5}{3}n + c\text{,}$$ where $c$ depends on time complexity of base case $T(1)$, so $n\leq T(n) \leq 2n +c$ and therefore $T(n)\in \mathcal{O}(n)$.