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

• So $T(n)=O(logn)$ or $O(n)$. I'm confused with how the others got a different answer. Are there multiple ways that result in different answers? – GiBiT 09 Oct 7 '13 at 15:42
• It's consistent with, and sharper than, the other answers. It says that $T(n)$ is, up to a logarithm-sized error term, equal to the linear function $5n/7$ (and this function plus its logarithmic correction is certainly $O(n)$). The $O()$ notation is well explained at Wikipedia and is very useful for all asymptotic questions. – zyx Oct 7 '13 at 15:52

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

• So case3 is the correct case. Because $n^1 = n$, Therefore $T(n) = O(n)$. Sorry I'm really new at this, and my professor confused the hell out of me. – GiBiT 09 Oct 7 '13 at 15:13
• Do I need to add/subract an $\epsilon$ if it is a whole number? – GiBiT 09 Oct 7 '13 at 15:16
• There is an obvious guess as to the precise asymptotics and things are easy once that is in place. – zyx Oct 7 '13 at 15:33
• "Do I need to add/subract an ϵ if it is a whole number?" Sorry but I do not understand your question? Where exactly do you want to add or substract an ϵ? – Did Oct 7 '13 at 16:17

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

• What happens if T(1)=42? – Did Oct 7 '13 at 15:02
• @Did You are right, thanks, I forgot the base case (In your case, let be $c = 42$;) ). – Antoine Oct 7 '13 at 15:15