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
    Thanks Frank Science. it is the same as you have suggested. But how to resolve it?2012-06-16

3 Answers 3

2

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.

1

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.

0

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.