I did not understand this question

#1

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

n

log n

n+1

None of these

#2

n should be the correct answer.

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

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

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

T(n - 3) = T (n - 4) + T(n - 5) - T(n - 6)

T(n - 4) = T (n - 5) + T(n - 6) - T(n - 7)

…

…

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

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

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

On Adding all the above recurrences, all the red terms of a recurrence will be cancelled out with the red terms of consecutive recurrences, similarly all the blue terms of a recurrence will be cancelled out with the blue terms of consecutive recurrences.

Thus we get

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

but since T(3) =3 & T(1) = 1

so our final recurrence will be T(n) = T(n - 2) + 2

Solution of T(n) = T(n - 2) + 2 will be n.

if you have more doubts regarding this feel free to ask
i hope this helps
if yes hit a like and don’t forgot to mark doubt as resolved :grinning:

#3

This solution is given in the next slide.

I wanted you to explain me this question properly. I did not understand the question.

#4

question is straight forward
T(n) = T(n - 1) + T(n - 2) - T(n - 3), if n > 3
T(n)=n otherwise

now you have to told the time complexity order

which comes out to be O(n) as solved above

i hope question and answer is clear now
please mark doubt as resolved