- A
The randomized algorithm runs in O(n

^{2}) 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

37. Consider the randomized find algorithm. Which of the following statements are true?

- 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.

- Option : C
- Explanation : Option A and C both are correct.

You must be logged in to post a comment.

You must be logged in to post a comment.

You must be logged in to post a comment.