Advanced Algorithm Q.37
0. 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.
