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

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


2. Which decision procedure has at least doubly exponential time complexity?

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


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

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


4. Which of the following shows the correct relationship among some of the more common computing times for algorithms?

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *


5. F(x) = (7x6 + 3x4 + 17x + 9)/(0.01x3 * x-1) is Big - O of WHAT?

Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *