Randomization, either in running time or in accuracy of an algorithm, improves the theoretical value of upper bound on time complexity of any algorithm by a significant factor.
We know that the best sorting algorithm is Quick Sort. But, can you argue why Quick Sort is best as compared to Merge Sort and Heap Sort? As we know that all of these three algorithms have best case time complexity as O(nlogn). Also, if we consider the worst case time complexity of Merge Sort and Heap Sort, both are same as O(nlogn) but worst case time complexity of Quick Sort is O(n^2). The answer to this is actually given by space complexity issue. The Quick Sort algorithm sorts the given set of numbers ‘in-place’ while other two require some extra space for sorting procedure. Actually much extra time is spent in accessing this extra space if we actually execute these algorithms on any computer. But, are you convinced that Quick Sort is better than Merge Sort or Heap Sort? I guess ‘NO’. Because O(n^2) is always much worse than O(nlogn).
The correct explanation to above argument can be given by the concept of Randomization in Algorithms. The field of Randomized Algorithms say that, the possibility that Quick Sort undergoes worst case execution is very less. Suppose someone tells you that probability that time taken by Quick Sort on any randomly generated input exceeds 8(nlogn) is very less (actually this probability is proved to be less than 1/n^2 ). Let’s Take an example, for n=1000, the probability that time taken by Quick Sort on any randomly generated input exceeds 8(nlogn) is less than 0.000001. And, 8(nlogn) is equal to O(nlogn). So, you can see that above statement makes sense. This explains why the performance of Quick Sort is most of the times better than Merge Sort and Heap Sort (if we keep in mind the time taken by Merge Sort and Heap Sort while accessing extra required memory). Experiments performed on different values of n also agree with the proved result.
Currently, Randomized Algorithms have started replacing traditional deterministic algorithms as they perform better. There is a probability that the expected upper bound on randomized algorithm doesn’t hold but, it can be easily proved that such cases occur with very less probability.
- AmitHK
