Data Structures and Algorithms - Advanced Algorithm

The randomized algorithm runs in O(n²) time on all inputs.

There are some inputs on which the randomized algorithm never gives an incorrect answer

There are some inputs on which the randomized algorithm never gives an correct answer.

For some inputs ,the probability that the randomized algorithm gives an incorrect answer is greater than 0.5

On all inputs the expected running rime of the algorithm in O(n).

There are some inputs on which the algorithm performs poorly, i.e. the expected running time is not O(n).

The expected number of recursive calls to the randomized find routine is O(log n).

There is a small but non zero probability that the randomized find returns an incorrect answer.