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)