# Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences

>>>>>>>>Performance Analysis of Algorithms and Recurrences

• Option : D
• Explanation :
I). true
II). false, because recursive programs are use stack
III). true , best and avg O(nlog2n) and worst O(n2)
IV). false, because binary search default find mid element O(log2n) when use linear linked list find mid element O(n)

• Option : A
• Explanation :
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)

• 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.