Question

He running time of an algorithm is given by t(n) = t(n-1) + t(n-2) t(n-3), if n > 3 = n, otherwise then what should be the relation between t(1), t(2) and t(3), so that the order of the algorithm is constant ?

Answer 1

This is one where expanding a few terms can help:

T(1) = 1

T(2) = 2

T(3) = 3

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

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

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

The general pattern here seems to be that T(n) = n. We can formalize this with induction:

T(1) = 1, T(2) = 2, and T(3) = 3 by definition.

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

Hope this helps!

please mark it as a brainlist please