Write short notes on randomized Algorithm.

Subject: Analysis Of Algorithm

Topic: Introduction To Analysis Of Algorithm

Difficulty: High

aoa(14) • 5.1k  views
  1. 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.

enter image description here

  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.

enter image description here


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.


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

Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.


Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More