0

Which method should I use and how can I solve this recurrence to find the complexity (order) of the recurrence relation?

The equation is: $T(n) = 4T(n-1) - 3T(n-2) +1$

Find $O(T(n))$.

Benjamin Wang
  • 3,920
ShooterLens Aim
  • 3
  • Welcome to Mathematics Stack Exchange. Are you given initial conditions ($T(0)$ and $T(1)$)? – J. W. Tanner Jun 14 '20 at 13:49
  • Initial conditions don't affect complexity (except degenerate cases). – DanielV Jun 14 '20 at 13:50
  • Are you able to solve any kind of linear recurrence? If you don't know how to solve any linear recurrences, then what you need is a lecture not a math stack exchange answer, so your question would be out of the scope of this website. – DanielV Jun 14 '20 at 13:50
  • İt goes very confusing to me when i try to solve it, so yes i don't able to solve linear recurrence like that. – ShooterLens Aim Jun 14 '20 at 13:56
  • Have you looked for other similar questions? – rtybase Jun 14 '20 at 13:57
  • 1
    @rtybase Yes i did but i'll have look at again, maybe it's easy to find out the solution for you but i don't have any background on this kind of recurrences, so im sorry if i asked a horrible question, i'll learn how to ask a question properly. – ShooterLens Aim Jun 14 '20 at 14:03
  • I am sorry, @ShooterLensAim why did you accept the answer below? It's a very bad solution in terms of complexity! It mentions no caching to help you solve the problem in constant time, i.e. $O(1)$. – rtybase Jun 14 '20 at 14:15
  • @rtybase Since i don't know the way of solve that problem i can't know which solution is good for me, if you solve the problem then i can accept your answer. – ShooterLens Aim Jun 14 '20 at 14:21
  • Of course you do know a solution. Build a recurrent function in your favorite programming language that at each step will add 3 values, 2 being computations of step(n-1) and step(n-2) respectively. Like with Fibonacci. That will lead to $O(2^n)$. But if you apply caching, it will be $O(n)$ (linear, I was wrong in my previous comment, it's linear). – rtybase Jun 14 '20 at 14:26

3 Answers3

1

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

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

subtract:

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

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

Now you have a homogeneous recurrence relation. Do you know how to solve that?

J. W. Tanner
  • 60,406
1

$$T(n)-4T(n-1)+3T(n-2)=1~~~(1)$$ After @J. W.Tanner 's suggetion Put $T(n)=x*n$ in $$T(n)+5T(n-1)-7(n-1)+3T(n-2)=0~~()$$ We get $x=3,1,1$, So $$T(n)=C_1 (3)^n+(C_2 n + C_3)1^n~~~(3)$$ By putting (3) in (1), C_2=-1$b %C_1$ and $C_3$ are undetermined. So h fnl luos $$T(n)=C_1 3^n+C_3-n/2.$$

Z Ahmed
  • 43,235
0

We have

$$T(n) - 4T(n-1) + 3T(n-2) = 1. \qquad \cdots (1)$$

We solve it like we solve differential equations, by summing a complementary function $C(n)$ and a particular solution $P(n)$, where $C$ solves the homogeneous equation

$$T(n) - 4T(n-1) + 3T(n-2) = 0, \qquad \cdots (2)$$

and $P$ is any solution to (1).

Can you continue? Do you know what is an eigenfunction to (2)?

The characteristic equation is $x^2-4+3=0$, so $(x-3)(x-1)=0$.

Thus $C(n) = A\cdot 3^n + B\cdot 1^n$, where A and B are constants, to be determined by initial data (such as T(0), T(1)).

Now, we may try to find a particular solution. We usually start by trying constants. However, constants can only solve the homogeneous equation in this case, so we proceed to try linear functions $P(n) = c\cdot n$. According to a helpful commenter Zarrax, we get $ c = -1/2$.

However, you only care about the complexity (order) of the solution. So yeah, clearly the order is $O(3^n)$

Benjamin Wang
  • 3,920
  • The particular solution is not a constant here since constants solve the homogeneous equation. Instead you try $T(n) = cn$ and solve for $c$, in this case getting $c = -{1 \over 2}$. – Zarrax Jun 14 '20 at 14:03
  • 1
    Thanks sir, so the solution is 3^n ? – ShooterLens Aim Jun 14 '20 at 14:07
  • @Zarrax Sorry! I will edit! – Benjamin Wang Jun 14 '20 at 14:07
  • 1
    @BenjaminWang hi, i understand (x−3)(x−1), but could't figure out where C(n) coming from – ShooterLens Aim Jun 14 '20 at 14:39
  • @ShooterLensAim Define the difference operator $D$ such that $D(a_{n}) = a_{n+1}$. Then, this operator has an eigenfunction $a_n=k^n$ because $D(a_n) = D(k^n) = k^{n+1} = k \cdot k^n = k \cdot a_n$. You can see that the eigenvalue is $k$ (there can be multiple different $k$ that works), which can be found by solving the characteristic equation I showed above (The reason is that you can just substitute $a_n$ into (2) in my answer, and then cancel throughout a factor of $k^n$). – Benjamin Wang Jun 15 '20 at 12:34