0

I have a recurrence relation:

T(n)= 3T(n-1)-2T(n-2) Where n>1 .

note when 1, n=1. and when 0, n=0 .

Find a tight bound for T(n). How do I now prove that it's big O and Ω in order to prove it's tight bound

Not really sure how to solve this. Any help would be greatly appreciated, thanks!

Hani
  • 11
  • Note that $3T(n-1) > T(n) > 3(T(n-1)-T(n-2))$. Now, use these bounds to make a conclusion. – Sarvesh Ravichandran Iyer Sep 26 '16 at 02:29
  • Show your attempt. What have you tried? What do you think? – Mayank Deora Sep 26 '16 at 02:32
  • Why not just solve the linear recurrence in this particular case? – dxiv Sep 26 '16 at 02:33
  • This is a linear recurrence. Look to the characteristic polynomial of the recurrence, which in this case is $x^2-3x+2=0$. Factor that to find $(x-2)(x-1)$ which implies that $T(n)=a\cdot 2^n + b\cdot 1^n$ for some specific values of $a$ and $b$ which are dependent on the initial conditions. – JMoravitz Sep 26 '16 at 02:34
  • If the initial conditions are $T(1)=1$ and $T(0)=0$ then you have $T(n)=2^n-1$ – iamvegan Sep 26 '16 at 02:34
  • yes I solved in order to prove by induction and I got T(n)=2^n−1. I'm not sure how to improve tight bound – Hani Sep 26 '16 at 02:38
  • 1
    Well if you ask me $T(n)\leq 2^n -1$ is a very tight bound but I don't know. – iamvegan Sep 26 '16 at 02:43
  • Once you determined that $T(n) = 2^n - 1$ it trivially follows that $T(n) = \Theta(2^n)$ i.e. both $\mathcal {O}$ and $\Omega$. – dxiv Sep 26 '16 at 02:46
  • @dxiv So I don't need to prove that ? or how it's equal to Big O and Ω – Hani Sep 26 '16 at 02:48
  • $lim_{n \to \infty} T(n) / 2^n = 1$ implies (and is in fact stronger than) $T(n) = \Theta(2^n)$. What parts precisely you have to prove depends on what you know already and are allowed to use, which I can't guess. – dxiv Sep 26 '16 at 02:51

0 Answers0