When do Randomized Algorithm performs best?
What is Randomized Algorithm?
Basically we use random algorithm which typically gives any random number or value as an input to our executing program to decide what to do next anywhere in our logic.
This algorithm is used to reduce the time complexity, memory used or space complexity, in a standard algorithm to guide its behavior, and also achieving good performance in “Average Case” over all possible choices of random value.
This figure clearly specifies that whenever our logic stuck, a random value is given to our algorithm as an input or with input to get an output.
Classification of Randomized Algorithm
1. Las Vegas algorithm
It was introduced by László Babai in 1979, this randomized algorithm produces either correct output, or no output when no result is found, but it cannot guarantee a time constraint. Time complexity is not fixed (not deterministic), it can vary for the same input. It does, however, guarantee an upper bound in the worst- case scenario.
Las Vegas is a randomized algorithm that use the random input to give the correct output or no output, but the is finite and may vary for the same input.
Let’s consider a simple example that is Randomized Quick Sort.
What is Randomized Quick Sort?
As everyone knows Randomized Quick sort I will explain it in short. It uses partitioning procedure, in which you will be given an n sized array, you will choose any element from that array as a pivot element then it will divide that array into two subarrays. Elements which are larger than that of pivot element will the placed in right subarray and the smaller will be at left subarray. In the given example 4 is taken as the pivot.
If you continue this partitioning procedure recursively to left sub array and right subarray until you reach subarrays of size 1, you will obtain a sorted array.
The average runtime of quick sort algorithm is O(n log n ). Here I am not explaining whole Quick Sort. There are many more blogs which explains in depth. Here Analysis of partitioning procedure matters, to be more specific, how are we going to select the pivot element.
You can choose any element but firstly let’s consider the deterministic approach, so we will choose first or last element as pivot elements. Let’s take first element. Consider best case, when we do partition procedure it will divide the array into two subarrays of the same size. But what about worst-case?
Worst Case occurs when array is already sorted. The left subarray will always be empty in each iteration, and the right subarray contains all the elements except the pivot. So, at each step, we will have to partition arrays of size n, n-1, n-2, n-3, …, which we add up to O(n²) time-complexity.
The Reverse will happen for pivot as last element. Worst case for this will occurs when array is sorted in descending order. The left subarray will always be empty in each iteration, and the right subarray contains all the elements except the pivot. So, here also O(n²) will be the time-complexity.
How to this situation? This can be solved by avoiding deterministic approach. So, instead of using the first or last element, we will randomly select an element to be the pivot. If the algorithm selects the pivots uniformly at random, the algorithm shall produce reasonably balanced subarrays regardless of the input arrays.
Even though you select the pivot randomly, your subarrays may not be well-balanced. However, the possibility of this to occur will be very small compared to selecting the first item or last element. In fact, there is a very little deviation from the average case while using random pivots and you can check the proven probabilistic analysis of randomized quicksort from here if you are interested. You can even test it yourself by generating random arrays.
2. Monte Carlo algorithm
It was introduced by Stanislaw Ulam in late 1940s, this randomized algorithm is a probabilistic algorithm which, may not give correct answer but the running time for these algorithms is fixed. There is also generally a probability guarantee that the answer is right.
Monte Carlo randomized algorithm is an algorithm which have a chance of producing an incorrect result, but the run time is fixed.
Let’s consider the example of Karger’s algorithm for Min Cut
Basic work of the Karger Algorithm is if we have given the graph and if we want to divide that graph into two graphs
For Example: Let’s say we have graph(G) and we have to divide graph in two graphs s1 and s2
If we want to divide that graph(G) into 2 graphs we have to find minimum number of edges so that we can remove them so that graph G can get converted to two graph s1 and s2
In the above figure you can see that I have removed the edge a1 and a4 so that now we have two graphs one with name s1 with vertex 0 and second s2 graph in which we three vertices with name 1,2 and 3. In this above example as you all are seeing that I have removed the 2 edges and in given graph (G) there are min 2 edges need to be removed if we want to convert it into the graph s1 and s2. How to remove the edges? & How contraction is done? and what is contraction? that we need to understand first before going towards the Karger Algorithm part.
Contraction: In the contraction what we do is that we combine two and consider them as single vertex.
Let’s say we have the graph (G)
For contraction if we want to remove vertex 1 then we will combine it with vertex 3 and (3,1) will be consider as the single vertex. Like this;
And the edges which were from Vertex 2 to Vertex 1 now will from Vertex 2 to Vertex (3,1). The Edge q1 from Vertex 1 to Vertex 3 will be permanently removed and previous edge from Vertex 2 to Vertex 3 will remain as it is.
This is how contraction is done. This all are the prerequisite in order to learn how Karger Algorithm actually work.
Karger Algorithm for finding Min-Cut
The basic use of this algorithm is that it will randomly pick any edge and then it will contradict it to another vertex and this process will continue until two vertices are left. At the end we will get minimum number of edges that are required to divide two graphs.
Consider the same example of dividing a graph(G) into two graphs S1 and S2.
To convert given graph into S1 and S2 graph we will randomly pick any edge then we will remove it as in this case we will remove the edge q5 which connects the Vertex 0 and 3. Then our graph will look like this,
Here I have done contraction as mentioned earlier, and we have to continue this contraction until we are only left with two vertices. So, for this we will select a random edge and again combine two vertices.
As here in the given graph only two vertices are remaining and number of edges that connects these two vertices are 2, so here what we conclude is minimum three edges we need to remove in order to convert this Graph G into Graph S1 and S2.
But in this case, it has given the correct output but there are some cases in which it will also give us the wrong output as it is random algorithm so it can pick different edges at the different time to contradict and so because of that it can also give us the wrong output.
Here, we will choose a 4 as random edge and will remove it by contradicting.
Then again, we will choose a2 as random edge and remove it by contradicting the vertices 2 and 3 then the graph will look like as shown in the below graph diagram,
Since only two vertices are left then we will stop Karger algorithm here. By seeing this above ending condition, it tell us that we must remove 2 edges. But it should be 3 as we have proved earlier.
So, this was the example of Monte Carlo algorithm for wrong output which says that this type of algorithms may or may not give correct result.
Let’s summarize what we understood till now!
We use randomized algorithm which typically gives any random number or value as an input to our executing program to decide what to do next anywhere in our logic.
Specifically, we use Las Vegas algorithm when we need correct output and reduce the time complexity by using random numbers as a input. But it doesn’t guarantee to run within specific time constraint. On the other hand Monte Carlo is a probabilistic algorithm which may produce wrong output but it runs only for specific amount of time.
Authors: Aditya Wanjari, Mohit Lalwani, Nitesh sonawane , Anushka Wankhade, Shresthi Yadav
References