246 OTHER ALGORITHMIC TECHNIQUES
This function randomly picks an element and checks to see if it appears in a
majority of locations. This algorithm is considered to be true-biased because if
the algorithm returns true, it means we found the majority element, so true is
absolutely correct. But if it returns false, it is possible we picked the wrong ele-
ment and that there still is a majority element. If there is a majority element,
the chance of picking a minority element is less than 50% and gets smaller the
more that the majority element appears. This still means that it is possible that
this algorithm might be correct only 50% of the time in some cases. If we call
Majority five times, the algorithm improves to 97% correct, and the com-
plexity would be just 5N, or O(N).Monte Carlo Prime Testing
We can check to see if a number N is prime by using a Monte Carlo algo-
rithm. In this case, we generate a random number between 2 and and see
if it divides evenly into N. If it does, N is not prime; if it doesn’t, we can’t be
sure. This algorithm is not very good because it will return false frequently. For
example, if we consider the number 60,329, which is the product of the three
prime numbers 23, 43, and 61, the algorithm will generate a random number
between 2 and 245, but only three numbers in this range will produce the cor-
rect answer. This has a 1.2% chance of being correct.
Although this simple algorithm will not do very well, there are other similar
techniques that are beyond the scope of this book that will solve this problem
with a higher probability of correct answers.■ 9.2.3 Las Vegas Algorithms
Las Vegas algorithms will never return the wrong answer but sometimes will
return no answer at all. The longer these algorithms run, the higher their prob-
ability of success. The basic idea is that a Las Vegas algorithm will randomly
make decisions and then check to see if they have resulted in a successful
answer. A program that uses a Las Vegas algorithm would repeatedly call it until
the algorithm indicated success. If we say that success(x) and failure(x) are the
times necessary to calculate a successful or unsuccessful answer, respectively, for
input of size x, and we say that p(x) is the probability that the algorithm will be
successful, we get the following equation:
time(x) = p(x)* success(x) + (1 p(x))* (failure(x) + time(x))N