Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You might want to look at the answers to some of the numerous very similar questions already on the site. –  Did Jun 16 '12 at 10:44
    
What is $T$ ? if it is a sequence what about the case $n$ is odd ? –  Mohamed Jun 16 '12 at 10:54
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$. –  Frank Science Jun 16 '12 at 11:32
    
@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)$. –  Did Jun 16 '12 at 11:35
    
@user900168: This new version still leaves infinitely many arbitrary choices. (And thus infinitely many solutions.) –  Dejan Govc Jun 16 '12 at 11:44

3 Answers 3

As others have stated, you need to make additional assumptions to find a unique solution. I will assume that you want to find an approximate equivalent to some discrete relation defined over the integers, and therefore you are looking for a simple function defined over reals that satisfies this continuous relation.

For this purpose, a natural constraint is to require that $T$ is a polynomial defined over the reals. Let $a_k x^k$ be the leading coefficient of $T$ ($k\ge 1$). Then we must have: $$a_k=2a_k/2^k$$ hence $k=1$ because $a_k\ne 0$. So $T(n)=an+b$, and the relation $$an+b=2\left(a\tfrac n 2+b\right)+2$$ is satisfied iff $b=-2$.

And because $T(2)=1$, $a=3/2$, giving the equation you were looking for.

share|improve this answer
    
Thank you very much –  user900168 Jun 17 '12 at 16:33

The recurrence equation tells us nothing about the relation between odd terms. Since the even terms are completely determined by the choice of the odd terms, we can choose odd terms arbitrarily. Then we can calculate the even terms from the recurrence as follows, for $m$ odd:

$$\begin{align}a_{2^n m} &= 2a_{2^{n-1}m}+2=\\&=2^2a_{2^{n-2}m}+2^2+2=\\&=\cdots=\\&=2^na_m+2^m+2^{m-1}+\cdots+2=\\&=2^n a_m + 2^{m+1}-2\end{align}$$

All solutions are of this form. To justify the calculation rigorously, use mathematical induction.

share|improve this answer

First we need to check if $f(n)\in\mathcal{O}(n^{log_{b}{(a)}-\epsilon})$, for some $\epsilon\gt0$:

Using the Master Theorem, with $a=2$, $b=2$, $f(n)=2$, $log_{2}{2}=1$:

$$2\in\mathcal{O}(n^{1-\epsilon})$$

Choosing $\epsilon=1$, we get:

$$2\in\mathcal{O}(1)$$

Which holds, so using the Master Theorem, we can determine that:

$$T(n)\in\mathcal{\Theta}(n)$$

Bear in mind that a solution is not possible as we do not have any information about the starting point of the sequence, so we can only determine the growth of the sequence.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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