Randomized algorithm

Deterministic algorithm is an algorithm in which for given particular input it will always produce the same output, with the underlying machine always passing through the same sequence of states as shown in figure 1.

1. To overcome the computation problem of exploitation of running time of a deterministic algorithm, randomized algorithm is used.
2. Randomized algorithm uses uniform random bits also called as pseudo random number as an input to guides its behavior (Output).
3. Randomized algorithms rely on the statistical properties of random numbers. One example of a randomized algorithm is quicksort.
4. It tries to achieve good performance in the average case.
5. Randomized algorithm is also called as probabilistic algorithm.
6. Randomized algorithm flow steps is shown figure 2.

Example:

The problem of finding ‘a’ in an array of n elements:

In a given array of n elements let half elements are ‘a’ and that of half are ‘b’. One approach of the approach is to look at each element of the array and this is an expensive one and will take n/2 operations, if the array were ordered as ‘b’s first followed by ‘a’s. With this approach we cannot guarantee that the algorithm will complete quickly.

Using randomized algorithm, if we look randomly then we can find ‘a’ quickly with high probability.

Advantage of Randomized Algorithm:

1. The algorithm is usually simple and easy to implement.
2. The algorithm is fast with very high probability, and/or it produces optimum output with very high probability.

Uses:

Randomized algorithms are particularly useful when faced with a malicious attacker or “adversary”