The running time of an algorithm is given by T(n) = T(n-1) + T(n-2) - T(n-3) , if n>3

Question

Comments

sir can u solve this?

---

you can see the answer by Umang below. Just do the changes in it and you will get it.

---

what should be the relation between T(1),T(2),T(3) so that the algorithm time complexity  becomes constant?

Answer 1

Given recurrence relation

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

      =n otherwise

So we can write T(1)=1,T(2)=2 and T(3)=3 when n<=3

Now, putting T=4 in the given equation we get,

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

       =3+2-1=4

Similarly,T(5)=T(4)+T(3)-T(2)

                   =4+3-2=5

and T(6)=T(5)+T(4)-T(3)=5+4-3=6;

so in general,we get,T(n)=T(n-1)+T(n-2)-T(n-3)=(n-1)+(n-2)-(n-3)=n

Therefore,T(n)=o(n)

Comments

You are solving T(n) assuming that we have store the value of T(n-1), T(n-2), and T(n-3) but since we are not using dynamic programming here I doubt this is correct. For solving T(n) all its subproblems needs to be solved individually, in that case, I don't think that complexity will remain O(n). It should be exponential.

---

My solution is 100% correct.A problem can be solved in multiple ways.