Mr. Grummel Get the app
← All notes
LEARNING 5 MIN READ DRAFT — OCTOBER 2027

The algorithm that grabs the best option right now and never looks back

A greedy algorithm always picks whatever option looks best at the current step, never reconsidering an earlier choice, making it fast but only reliably optimal for certain kinds of problems.

A greedy algorithm builds up a solution step by step, and at each individual step it simply picks whatever available option looks best right at that moment, according to some straightforward local criterion, without ever going back to reconsider or revise an earlier choice once it's made. This makes greedy algorithms notably fast and simple to implement, since they never have to backtrack or explore alternative paths, but that same commitment to never reconsidering a past choice is exactly why a greedy algorithm doesn't reliably produce the truly best overall solution for every kind of problem.

Committing irreversibly to each local best choice is what makes greedy fast

Because a greedy algorithm never revisits a decision once it's made, it can move through a problem making just one pass, evaluating and committing to each choice exactly once, which is precisely what gives greedy algorithms their considerable speed advantage over approaches that have to explore or reconsider many different possible paths through a problem. This efficiency comes with a real structural cost, though: a choice that looks best locally, given only the information available at that specific step, isn't guaranteed to actually be part of the overall best possible solution once the full problem is considered.

Whether greedy actually works depends on the specific structure of the problem

Certain problems happen to have a mathematical structure, sometimes called the greedy-choice property, where making the locally best choice at each step is provably guaranteed to still lead to a globally optimal overall solution, and for exactly these problems, a greedy algorithm is not just fast but also reliably correct. Many other problems lack this convenient structural guarantee, meaning a greedy approach applied to them can produce a solution that's fast to compute but genuinely suboptimal, sometimes considerably worse than the true best answer — which is precisely why choosing a greedy algorithm for a given problem requires first confirming that the problem's underlying structure actually supports it, rather than simply assuming greedy will work.

A greedy algorithm builds a solution by always picking whatever option looks best at the current step, never reconsidering an earlier choice, which makes it fast but only reliably produces a truly optimal answer for certain kinds of problems.

What we're still unsure about

The basic mechanics of greedy algorithms, and the mathematical conditions under which they're provably guaranteed to produce an optimal solution, are precisely defined, well established computer science, confirmed through formal proof for the specific problem classes where greedy is known to work. What's more genuinely an ongoing area of algorithmic research is identifying exactly which new or less obviously structured problems actually satisfy the conditions needed for a greedy approach to be provably correct, since this isn't always apparent just from a problem's surface description — computer scientists continue to analyse newly encountered problems case by case to determine whether a greedy strategy can be proven safe for them, rather than there being one general test that instantly settles the question for any arbitrary problem.

This sits inside Greedy Algorithms, one of eight topics in Algorithms, one of seven domains in Computer Science, one of seventeen subjects the app can quiz you on.

Draft — not published yet.
Try the pop quiz