Error/complexity measures

• Las Vegas _ always correct, but may answer “don’t know” with some probability

• Monte Carlo _ may err, with some probability

• pemax _ worst case probability of error

• qemax _ worst case expected queries

• Exact _ pemax= 0

Previous slide

Next slide

Back to first slide

View graphic version