What is a Randomized Algorithm?

A randomized algorithm is defined as one that uses a certain amount of randomization in its logic or operation. It is said to be an algorithm that depends on the random number to perform its operation. It is used for reducing the overall time complexity, space complexity in the standard algorithm. The randomized algorithm uses the concept of random numbers to find the solutions to the different kinds of problems and also to improve the problem solutions.

The general working of the randomized select algorithm is to generate the random number (r) within the specified range and the decisions are made based on the r value. In the optimized problems, this algorithm provides the optimal solutions; compared to worst-case time complexity, the average-case time complexity is more important.

Example: Random number is used in randomized quick sort to select the next pivot (or the array will be shuffled randomly).

Classification

Randomized algorithms are divided into two types and they are:

• Monte carlo
• Las vegas

Monte Carlo

The Monte Carlo algorithm is defined as the randomized method whose result has a tiny chance of being erroneous. Monte Carlo is used for producing the optimum or correct results with a certain probability. These algorithms consist of the deterministic run time and it is quite easy to find the worst-case time complexity.

Example: Implementation of Karger’s algorithm allows the calculation of the minimum cut with the probability values; where the value must be greater than or equal to 1/n² (n represents the vertices). O(E) is the worst-case time complexity.

Las Vegas

The Las Vegas algorithm is defined as the randomized algorithm that consistently generates proper results or alerts the user to a failure. Las Vegas algorithm is used for producing the optimum or correct results. Depending upon the random values the time complexity is calculated and evaluated as an expected value. Randomized quicksort is used to sort the input array, O(n log n) is the worst-case time complexity.

Example: Quicksort is a common las vegas randomized algorithm. Quicksort is a sorting algorithm that sorts the elements with no extra usage of memory.

Quicksort vs Randomized Quicksort

Quicksort

Quicksort algorithm is based on divide and conquer. The simple and efficient approach for sorting is quicksort. In quick sort, a pivot element (X) is selected from the unsorted array A and divides the array is divided into two different subarrays namely,

• A_small – elements are smaller than X.
• A_large – elements are larger than X.

The subarrays are sorted recursively and then combined together in A_sorted.

Algorithm

• Quicksort(A)
  • If A consists of single element
    • Return A
  • X<- A1
  • Determine the elements A_small (smaller than X)
  • Determine the elements A_large (large than X)
  • Quicksort(A_small)
  • Quicksort(A_large)
  • Combine A_small, A_large, and X to A_sorted (single array).
  • Return A_sorted

Quicksort's processing time is determined by the size of the input array and partition technique. Quicksort can be improved by choosing X (pivot element) as a good splitter and can be proved by achieving O(n log n) runtime. The runtime can be achieved when both the subarray size needs to be at least n/4.

Randomized quicksort

The pivot element in randomized quicksort is chosen evenly at random from the array. Quicksort can be improved by selecting the X randomly. As half of the elements will be a good splitter, when X is selected randomly then there is only a 50% chance (X is a good choice). This randomized quicksort makes sure that input is received and the run time is small.

Algorithm

• RandomizedQuicksort(A)
  • If A consists of a single element.
    • Return A.
  • Select X randomly from A.
  • Determine the elements A_small (smaller than X).
  • Determine the elements A_large (large than X).
  • RandomizedQuicksort(A_small).
  • RandomizedQuicksort(A_large).
  • Combine A_small, A_large, and X to A_sorted (single array).
  • Return A_sorted.

It concatenates and recursively sorts the subarrays. O(m²) is the worst-case runtime and O(m log m) is the expected runtime. The expected runtime will be a good measure of randomized algorithms’ performance.

The major difference is that randomized quicksort selects the pivot element (X) randomly; whereas, in quicksort, X is selected from the unsorted array. Compared to quicksort the run time is small in randomized quicksort.

Uses

• Cryptography makes extensive use of randomised algorithms.
• Primality testing is an example of a number-theoretic application.
• Used in the verification of algebraic identities such as polynomial and matrix identities, as well as interactive proof systems.
• Minimum spanning trees, shortest pathways, and minimum cuts are examples of graph algorithms that employ it.
• It's utilised for things like deadlock prevention and distributed consensus in parallel and distributed computing.
• Another application is in derandomization, where a randomised algorithm is first devised, then it is argued that it may be derandomized to produce a deterministic method.

Advantages

• The algorithm is typically straightforward and straightforward to implement.
• The algorithm is quick with a high likelihood of producing the best results.
• Algorithms that are randomised are particularly efficient.
• When compared to deterministic algorithms, randomised algorithms have better asymptotic limits.

Disadvantages

• There is no assurance that the issue will be resolved.
• It does not always reach the global optimum solution.

Context and Applications

This topic is important for postgraduate and undergraduate courses, particularly for,

• Bachelors in Computer Science Engineering
• Associate of Science in Computer Science.

Practice Problems

Question 1: What is the efficient time complexity of Karger's algorithm, which uses a randomized algorithm in the Monte Carlo method?

1. O(n log n)
2. O(E)
3. O (Log n)
4. O(n)

Answer: Option b is correct.

Explanation: O(E) makes efficient use of the algorithm used in various developed applications for maintenance. It improves the efficiency of time complexity.

Question 2: Which sorting algorithm is efficient in the randomized algorithm?

1. Bubble sort
2. Merge sort
3. Quicksort
4. Selection sort

Answer: Option c is correct.

Explanation: Quicksort algorithm is used for the random purpose and it can be used efficiently which sorts numbers in either ascending or descending order.

Question 3: Can we use probability in the randomized algorithm?

1. Yes
2. No
3. Wrong statement
4. None of the above

Answer: Option a is correct.

Explanation: We can efficiently use probability mathematical structure in randomized algorithms. It will reduce the steps in a more detailed explanation of the system.

Question 4: What is the worst time case complexity of quicksort?

1. O(n log n)
2. O(E)
3. O(log n)
4. O(n)

Answer: Option a is correct.

Explanation: Quicksort has O(n log n) of time complexity when it is used in a randomized algorithm. However, it can be used efficiently which sorts numbers in either ascending or descending order.

Question 5: Randomized algorithm is classified into ___ types.

1. One type
2. Two types
3. Three types
4. Four Type

Answer: Option b is correct.

Explanation: The algorithm is classified into two types that are Las Vegas and Monte Carlo. It is mostly used to reduce the number of steps and solve the problem with lower time complexity.