In a randomized algorithm (probabilistic algorithm), we make some random choices.
2 types of randomized algorithms:
1. For an optimization problem, a randomized algorithm gives an optimal solution.
The average case time-complexity is more important than the worst case time-complexity.
2. For a decision problem, a randomized algorithm may make mistakes.
The probability of producing wrong solutions is very small.
This problem can be solved by the divide-and- conquer approach in O(nlogn) time.
The randomized algorithm: partition the points into several clusters:
We only calculate distances among points within the same cluster.
Similar to the divide-and-conquer strategy. There is a dividing process,
but no merging process.