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

22 Which of the following statements is true?
I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient
III. The worst case complexity for Quicksort is O(n² )
IV. Binary search using a linear linked list is efficient.

I). true
II). false, because recursive programs are use stack
III). true , best and avg O(nlog₂n) and worst O(n²)
IV). false, because binary search default find mid element O(log₂n) when use linear linked list find mid element O(n)

23 The running time of an algorithm is given by
T(n) = T(n - 1) + T(n - 2) - T(n - 3), if n > 3
n, otherwise.
The order is

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)

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

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.

25 Time complexity of an algorithm T (n), where n is the input size is given by
T(n) = T(n - 1) + 1/n, if n>1;
= 1, otherwise
The order of this algorithm is