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

1. A hash function randomly distributes records one by one in a space that can hold x number of records. The probability that the mth record is the first record to result in collision is

  • Option : A
  • Explanation :
    Probability for the first record not colliding is x/x.
    Probability for the second record not colliding is x-1/x.
    (This is because one place is already occupied, So, favorable number of cases is x-1).
    Probability for the third record not colliding is x-2/x.
    Probability for the (m-1)th record not colliding is .
    Now the next (mth) record is resulting in a collision. Out of the x places, it should has to one of the (m-1) places already, filled. So,
Cancel reply
Cancel reply

3. The running time T(n), where 'n' is the input size of a recursive algorithm is given
    T(n) = c + T(n-1), if n > 1
      = d, if n ≤ 1
The order of the algorithm is

  • Option : B
  • Explanation :
    Recursively applying the relation, we finally get
        T(n + 1) = c(n - 1) + T(1)
            = c(n - 1) + d
    hence order is n.
Cancel reply
Cancel reply