PA of Algorithms Q24

24The 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?

Option : A
Explanation :
For sufficiently large n,
T(n)=Tn−1)+T(n−2)−T(n−3).
If the order of the algorithm for which above recurrence is applicable for the time complexity, is a constant,
T(n)=T(n−1).
⟹T(n)=T(n)+T(n−2)−T(n−3)
⟹T(n−2)=T(n−3)
Going like this, we must have T(1)=T(2)=T(3) which is option A.

Forgot your password?

I agree with the Terms.