When do Randomized Algorithm performs best?

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.

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.

  1. https://www.geeksforgeeks.org/randomized-algorithms/
  2. https://brilliant.org/wiki/randomized-algorithms-overview/
  3. https://www.quora.com/What-is-the-differenc-between-Monte-Carlo-and-Las-Vegas-algorithm-and-where-we-use-them-in-rabin-karp-algorithm
  4. https://en.wikipedia.org/wiki/Randomized_algorithm

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store