A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an input to guide its behavior. Formally, the performance will be a random variable determined by the random bits, thus either the running time. In the second case, random performance and random output, the algorithm for a procedure is somewhat questionable. In the case of output, it is no longer formally effective. However, in cases, probabilistic algorithms are the only practical means of solving a problem. As a motivating example, consider the problem of finding an ‘a’ in an array of n elements, input, An array of n≥2 elements, in which half are ‘a’s and the other half are ‘b’s. Output, Find an ‘a’ in the array and we give two versions of the algorithm, one Las Vegas algorithm and one Monte Carlo algorithm. Las Vegas algorithm, This algorithm succeeds with probability 1, after k iterations, the probability of finding an ‘a’ is, This algorithm does not guarantee success, but the run time is bounded. The number of iterations is less than or equal to k. Taking k to be constant the run time is Θ, Randomized algorithms are particularly useful when faced with a malicious adversary or attacker who deliberately tries to feed a bad input to the algorithm such as in the Prisoners dilemma. It is for this reason that randomness is ubiquitous in cryptography, in cryptographic applications, pseudo-random numbers cannot be used, since the adversary can predict them, making the algorithm effectively deterministic. Therefore, either a source of random numbers or a cryptographically secure pseudo-random number generator is required. Another area in which randomness is inherent is quantum computing, in the example above, the Las Vegas algorithm always outputs the correct answer, but its running time is a random variable. The Monte Carlo algorithm is guaranteed to complete in an amount of time that can be bounded by a function the size and its parameter k. Observe that any Las Vegas algorithm can be converted into a Monte Carlo algorithm, by having it output an arbitrary, Computational complexity theory models randomized algorithms as probabilistic Turing machines. Both Las Vegas and Monte Carlo algorithms are considered, and several complexity classes are studied, the complement class for RP is co-RP. Problem classes having algorithms with polynomial time average case running time whose output is always correct are said to be in ZPP, the class of problems for which both YES and NO-instances are allowed to be identified with some error is called BPP
Figure 1: Contraction of vertex A and B
Figure 2: Successful run of Karger’s algorithm on a 10-vertex graph. The minimum cut has size 3 and is indicated by the vertex colours.