A randomized algorithm makes random choices during the course of its execution. It is contrary to a deterministic algorithm whose execution is determined by its input. It is also possible to think of a randomized algorithm as a probability distribution on a deterministic algorithm.

Randomized algorithms can be classified into two groups:

  • Monte Carlo algorithms - may produce incorrect results but with bounded error probability.
  • Las Vegas algorithms - always produce correct results but with variation in its running time.

An example of a randomized algorithm is sorting by random sampling:

S is a set of numbers. Every number in S has an equal probability of being chosen.

Steps to sort the numbers in the set S in increasing order:

  • Choose a number n from S.
  • Compare each number in S with n. This yields two subsets:
    • S1 - contains numbers smaller than n.
    • S2 - contains numbers larger than n.
  • Recursively sort S1 and S2.
  • Output the sorted set S1, followed by n, and then the sorted set S2.

An example of a randomized data structure is a skip list:

The skip list is used to implement dynamic dictionaries with the following operations:

  • find the key
  • insert the key
  • delete the key

The standard solution involves the use of a binary search tree whose worst-case time per operation is O(log n), where n is the size of the dictionary. This requires rebalancing which results in significant overheads in the running time. The skip list overcomes these shortcomings and still performs the operations in expected time O(log n).

References:

[1] Allen B. Tucker. "Computer Science Handbook, Second Edition". Chapman and Hall/CRC, 2 edition, 2004