Randomized algorithms
In scenarios where computations are very expensive, introduction of randomness can help reduce computational effort at the expense of accuracy. The algorithms can be classified into the following and are depicted in Figure 9.7:
- Deterministic algorithms
- Randomized algorithm
Figure 9.7: Different types of algorithm structures
Deterministic algorithms solve the problem correctly where computational effort required is a polynomial of the size of the input, whereas random algorithms take random sources as input and make their own choices while executing.
Randomized algorithms for finding large values
The computational cost of finding the largest value in an unsorted list is O(n). Any deterministic algorithm will require O(n) effort to determine the maximum value. However, in scenarios where time is essence, and n is very large, approximation algorithms are used, which, instead of finding the actual solution, determine the solution that is closer to the actual solution...
