Which of the following options is INCORRECT about randomised algorithms?
ARandomised algorithms that always produce the same(correct)output for the same
input is known as Las Vegas Algorithms.
BRandomised algorithms whose output differs from run to run for the same inputs is
known as Monte Carlo Algorithms.
CThe execution time of Las Vegas Algorithm does not depend on the output of the
randomiser.
DA randomised algorithm is an algorithm in which some of the decisions made in the
algorithm depend on the output of the randomiser.
Show answerHide answer
Correct answer: (C) The execution time of Las Vegas Algorithm does not depend on the output of the
randomiser.
Explanation
Statement C is incorrect: a Las Vegas algorithm always gives the correct answer, but its running time depends on the random choices. A Monte Carlo algorithm has bounded time, but its output may vary or be wrong.