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
- coin change problem — The problem of making a given amount of money with the fewest coins from a set of coin values.
- brute force — Solving a problem by trying every possibility directly, without any clever structure.
Taught in
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers