Recurrence $T(n) = T({2n\over5}) +n$ using Master Theorem 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.

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)$.