Randomized algorithm: Difference between revisions

Revision as of 15:31, 1 April 2020

Revision as of 19:17, 22 April 2020

Line 20:

Las Vegas algorithm:

<sourcesyntaxhighlight lang="pascal">

findingA_LV(array A, n)

begin

Line 27:

until 'a' is found

end

</syntaxhighlight>

</source>

This algorithm succeeds with probability 1. The number of iterations varies and can be arbitrarily large, but the expected number of iterations is

Line 36:

Monte Carlo algorithm:

<sourcesyntaxhighlight lang="pascal">

findingA_MC(array A, n, k)

begin

Line 45:

until i=k or 'a' is found

end

</syntaxhighlight>

</source>

If an ‘''a''’ is found, the algorithm succeeds, else the algorithm fails. After ''k'' iterations, the probability of finding an ‘''a''’ is:

<div style="text-align:center;">