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

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

• A

O(n)  • B

O(n2)  • C

O(n3)  • D

O(3n2)  • A

I and II  • B

II and III  • C

I and IV  • D

I and III  • 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)

• A

n  • B

log n  • C

nn  • D

n2  • 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)

• A

T(1) = T(2) = T(3)  • B

T(1) + T(3) = 2T(2)  • C

T(1) - T(3) = T(2)  • D

T(1) - T(2) = T(3)  • 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.

• A

log n  • B

n  • C

n2  • D

nn  