3
$\begingroup$

I got stuck at the solution to the recurrence equation $T(n) = 2 T\left(\frac{n}{2}\right) + 2$.

Please give me a detailed explanation or references with detailed steps?

Sorry, I missed something.

If $n = 2$, then $T(n) = 1$; else if $n > 2$, then $T(n) = 2T\left(\frac{n}{2}\right) + 2$;

And a solution is suggested as: $$T(n) = \frac{3n}{2} - 2$$

Any comments about good books on recurrence relation? Thanks in advance.

  • 0
    You might want to look at the answers to some of the numerous very similar questions already on the site.2012-06-16
  • 0
    What is $T$ ? if it is a sequence what about the case $n$ is odd ?2012-06-16
  • 1
    @did But I think they're really wrong problems. $T(n)=2T(n/2)+2$ only constrains when $\log_2(x/y)\in\mathbb{Z}$. Perhaps $T(\lfloor n/2\rfloor)$ or $T(\lceil n/2\rceil)$ is right, or $T(x)$ is bounded when $0\le x<1$.2012-06-16
  • 0
    @Frank This *initial conditions* point has been made ad nauseam in previous posts. // The irony here is that introducing $T(n)=nS(n)-2$ yields readily $S(n)=S(n/2)$.2012-06-16
  • 0
    @user900168: This new version still leaves infinitely many arbitrary choices. (And thus infinitely many solutions.)2012-06-16
  • 0
    @did Your trick seems good, but in practice the running-time function is usually made up of $\lfloor n/2\rfloor$ or $\lceil n/2 \rceil$, for example, there's one possible: $T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+2$ and $T(0)=\alpha_0$, $T(1)=\alpha_1$.2012-06-16
  • 0
    Thanks Frank Science. it is the same as you have suggested. But how to resolve it?2012-06-16

3 Answers 3