3
$\begingroup$

If $T(n)= T(n-1) + 2T(n-2)$ with $T(0)=0$ and $T(1) = 1$

What is $T(n)$ (in $Θ$–notation) in terms of $n$?

I am trying to solve by substitution, but I am not sure if I am doing this right, as I get stuck. Can anybody tell me where to go from here?

$T(n)= T(n-1) + 2T(n-2)$

$T(n-1)= T(n-2) + 2T(n-3)$

$T(n-2)= T(n-3) + 2T(n-4)$

$T(n)= T(n-k) + 2T(n-(k+1))$

Substitute $n$ for $k$

$T(n)= T(n-n) + 2T(n-(n+1))$

$T(n)= T(0) + 2T(1)$

I am not sure where to go from here to find $T(n)$ (in $Θ$–notation) in terms of $n$.

$\endgroup$
  • $\begingroup$ What do you mean by "in $\theta$-notation"? $\endgroup$ – rogerl Jun 7 '15 at 22:23
  • $\begingroup$ @rogerl I believe the question is "for what $g(n)$ is $T(n) \in \Theta (g(n))$?". $\endgroup$ – Ken Jun 7 '15 at 22:25
  • $\begingroup$ Trying to find the $\Theta$ notation of the complexity of the algorithm. $\endgroup$ – Omar N Jun 7 '15 at 22:26
  • $\begingroup$ Whatever else, $T(n)= T(0) + 2T(1)$, a constant, cannot be right! $\endgroup$ – Simon S Jun 7 '15 at 22:26
  • 1
    $\begingroup$ @Ken I am just looking for the complexity in $\Theta$ notation. $\endgroup$ – Omar N Jun 7 '15 at 22:28
4
$\begingroup$

Generating functions for the win. Let $T(x) = \sum_{n=0}^{\infty}T_nx^n = \sum_{n=1}^{\infty}T_nx^n$, since $T_0 = 0$.

Then: $$\begin{split} T(x) &= x + \sum_{n=2}^{\infty}T_nx^n \\ &= x + \sum_{n=2}^{\infty}(T_{n-1} + 2T_{n-2})x^n \\ &= x + \sum_{n=2}^{\infty}T_{n-1}x^n + \sum_{n=2}^{\infty}2T_{n-2}x^n \end{split}$$

Let's rewrite those sums. The first one:

$$\begin{split} \sum_{n=2}^{\infty}T_{n-1}x^n &= x\sum_{n=2}^{\infty}T_{n-1}x^{n-1} \\ &= x\sum_{n=1}^{\infty}T_nx^n \\ &= xT(x) \end{split}$$

Likewise, the second sum works out to $2x^2T(x)$. Thus:

$$T(x) = x + xT(x) + 2x^2T(x)$$

So:

$$\begin{split} T(x) &= \frac{x}{1 -x - 2x^2} = \frac{x}{(1-2x)(1+x)} \\ &= \frac{\frac{1}{3}}{1-2x} + \frac{-\frac{1}{3}}{1+x} \\ &= \frac13\sum_{n=0}^{\infty}2^nx^n - \frac13\sum_{n=0}^{\infty}(-1)^nx^n \\ &= \sum_{n=0}^{\infty}\left(\frac{2^n - (-1)^n}{3}\right)x^n \end{split}$$

Which gives us our recurrence: $T_n = \left(\frac{2^n - (-1)^n}{3}\right) = \Theta(2^n)$

$\endgroup$
3
$\begingroup$
  1. $\Theta$-notation is?
  2. The difference equation provided is that which defines the Jacobsthal numbers.
  3. The general method to define the Jacobsthal numbers is as follows.

Let $T(n) = r^{n}$ in the difference equation $T_{n+2} = T_{n+1} + 2 T_{n}$ to obtain $r^{2} - r - 2 = 0$ which yields the solutions $2r = 1 \pm 3 \in \{4, -2\}$ and leads to the general form $$T_{n} = A \, 2^{n} + B (-1)^{n}$$. Using the values $T_{0} = 0$ and $T_{1} = 1$ then $$T_{n} = \frac{2^{n} - (-1)^{n}}{3}$$

$\endgroup$
  • $\begingroup$ And from this, $T(n) = \Theta(2^n)$. But presumably the OP wants to get this asymptotic info without fully solving. $\endgroup$ – GEdgar Jun 7 '15 at 22:43
1
$\begingroup$

we have $$t_n = t_{n-1} + 2t_{n-2}, t_0 = 0, t_1 = 2.$$ here are the first few numbers in the sequence: $$0, 2, 2, 6, 10, \cdots. $$

it looks like you can establish $$t_n > 0 \text{ for all } n \ge 1$$ by induction. once we have that can we use $$t_n \ge 2t_{n-2} $$ to conclude that $t_n = O(2^n)$ without solving the recurrence relation?

$\endgroup$
  • $\begingroup$ this is similar to my proof/my proof is correct? below. i think this establishes both upper and lower bounds and therefore Θ. $\endgroup$ – miniparser Jun 8 '15 at 15:38
0
$\begingroup$

i thought $2^n$ at first from similarity to Fibonacci #s.

from there it is just 2 trivial inductions to find for what $g(n)$ is $T(n)\in Θ(g(n)),$ because $T(n)\in Θ(g(n))$ when $T(n)\in O(g(n))$ and $T(n)\in$ (big omega)$(g(n))$, if i am not mistaken. And $T(n)\in O(g(n))$ when for some $c\in N,n_0\in Z$, $T(n)\le cg(n),n\ge n_0$. $T(n)\in $ (big omega)$(g(n))$ when for some $c\in N,n_0\in Z$, $T(n)\ge cg(n),n\ge n_0$.

$c=1,n_0=1$: base case: $T(1)=1\le 2^1$. Assume $T(n)\le (1)(2^n)$, $n\ge 1$. $T(n+1)=T(n)+2T(n-1)\le 2^n+2(2^{n-1})=2^n+2^n=2(2^n)=2^{n+1}$. so it holds by induction. similar proof for lower bound/big omega.

if i am not mistaken $2^n\Leftrightarrow log_2n$. $log_2n$ is the inverse of $2^n$ as $2^n$ is one-to-one.

edit: this part is incorrect: so is also $Θ(log_n)$.

$\endgroup$
  • $\begingroup$ Is $log_n$ the same thing as $2^n$? $\endgroup$ – Omar N Jun 7 '15 at 23:34
  • $\begingroup$ Huh? $\Theta(2^n)$ and $\Theta(\log n)$ are very different things. $\endgroup$ – Barry Jun 7 '15 at 23:44
  • $\begingroup$ Thats what I thought, but I was trying to reconcile how underdog's answer was different than the other two. $\endgroup$ – Omar N Jun 7 '15 at 23:48
  • $\begingroup$ @Omar, i beieve they are logically equivalent. $\endgroup$ – miniparser Jun 8 '15 at 15:08
  • $\begingroup$ is my solution correct, though? $\endgroup$ – miniparser Jun 8 '15 at 15:09

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.