How many examples do you need to see so that you have a given level of confidence that picking a hypothesis consistent with your observations will give you error less than E?
Suppose we have a finite set of hypotheses, H, and that we make m observations. If h is a hypothesis with error greater than E, then the probability that it will be consistent with a given observation is less than 1 - E, and the probability that it will be consistent with all m observations is less than (1 - E)m, which is less than exp( -Em ). Therefore the total probability that some hypothesis with error greater than E remains after m observations is less than |H|exp( -Em ). We can set this bound at some desired level, say d, and solve for m, giving
m > (ln |H | + ln (1/d) )/ E