Question

A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.

(a) worst case

(b) best case

(c) average case

(d) none of the mentioned

This question was posed to me in an online interview.

The query is from Randomized Algorithm in portion Other Classes Of Problems of Automata Theory

Answer 1

The correct answer is (c) average case

To explain: A randomized algorithm is an algorithm that employs a degree of randomness as a part of its logic using random bits as inputs and in hope of producing average case good performace.