counterexample

A single specific input that shows a claim or algorithm is wrong.

In more detail

One counterexample is enough to disprove a greedy strategy, as 6 with coins 1, 3 and 4 does for greedy coin change. Comparing a fast algorithm against brute force over many small inputs is an efficient way to find one.

Related terms

Taught in

References