It's me Bed.
Services
Works
13 Aug, 2019 Root User

### Randomized Algorithm:

• A probabilistic algorithm is an algorithm where the result and/or the way the result is obtained depend on chance. These algorithms are also sometimes called randomized algorithms.

• It makes use of randomizer(random number generator) to make some decision in a algorithm.

• The output and/or execution time of a randomized algorithm could also differ from run to run for the same input.

• It can be categorized into:

1. Las vegas algorithm

2. Monte carlo algorithm

Las vegas Algorithm

• this algorithm always same (correct) output for the same input.

• Execution time of this algorithm is characterized as a random variable.

• The execution time depends on the output of randomizer.

Monte Carlo Algorithm

``````<style type="text/css">
@page { size: 8.5in 11in; margin: 0.79in }
h3 { margin-top: 0.1in; margin-bottom: 0.08in; background: transparent; page-break-after: avoid }
h3.western { font-family: "Comic Sans MS", cursive; font-size: 14pt; font-style: normal; font-weight: bold }
h3.cjk { font-family: "Noto Sans CJK SC Regular"; font-size: 14pt; font-weight: bold }
h3.ctl { font-family: "Lohit Devanagari"; font-size: 14pt; font-weight: bold }
p { margin-bottom: 0.1in; line-height: 115%; background: transparent }
a:visited { color: #800000; so-language: zxx; text-decoration: underline }
a:link { color: #000080; so-language: zxx; text-decoration: underline }
</style>
``````

• Monte carlo is the algorithm whose output might differ from run to run for the same input.

• It may generate the wrong answer sometimes that depends on the output of the randomizer.

• The execution time is fixed.

Prosperous Nepal is possible only from technological innovation.