Data Structures and Algorithms - Performance Analysis of Algorithms and Recurrences

Avatto>>UGC NET COMPUTER SCIENCE>>PRACTICE QUESTIONS>>Data Structures and Algorithms>>Performance Analysis of Algorithms and Recurrences

21. , where O(n) stands for order n is

Cancel reply
Cancel reply

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(n2 )
IV. Binary search using a linear linked list is efficient.

  • 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)
Cancel reply
Cancel reply

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

  • 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)
Cancel reply
Cancel reply

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?

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