0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – GiBiT 09 Oct 7 '13 at 15:42
  • $\begingroup$ 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. $\endgroup$ – zyx Oct 7 '13 at 15:52
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – GiBiT 09 Oct 7 '13 at 15:13
  • $\begingroup$ Do I need to add/subract an $\epsilon$ if it is a whole number? $\endgroup$ – GiBiT 09 Oct 7 '13 at 15:16
  • $\begingroup$ There is an obvious guess as to the precise asymptotics and things are easy once that is in place. $\endgroup$ – zyx Oct 7 '13 at 15:33
  • $\begingroup$ "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 ϵ? $\endgroup$ – Did Oct 7 '13 at 16:17
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.