Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences
, where O(n) stands for order n is
- 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.
