- A The randomized algorithm runs in O(n2) time on all inputs.
- B There are some inputs on which the randomized algorithm never gives an incorrect answer
- C There are some inputs on which the randomized algorithm never gives an correct answer.
- D For some inputs ,the probability that the randomized algorithm gives an incorrect answer is greater than 0.5
Data Structures and Algorithms MCQ - Advanced Algorithm
- A On all inputs the expected running rime of the algorithm in O(n).
- B There are some inputs on which the algorithm performs poorly, i.e. the expected running time is not O(n).
- C The expected number of recursive calls to the randomized find routine is O(log n).
- D There is a small but non zero probability that the randomized find returns an incorrect answer.
