Algorithms For Dummies

Understanding why greedy is good

It shouldn’t surprise you that a greedy strategy works so well in the make-change 

problem. In fact, some problems don’t require farsighted strategies: The solution 

---

286

 

   

  PART 5 

 Challenging Difficult Problems

is built using intermediate results (a sequence of decisions), and at every step the 

right decision is always the best one according to an initially chosen criteria.

Acting greedy is also a very human (and effective) approach to solving economic 

problems.  In  the  1987  film  Wall Street,  Gordon  Gecko,  the  protagonist,  declares 

that  “Greed,  for  lack  of  a  better  word,  is  good”  and  celebrates  greediness  as  a 

positive act in economics. Greediness (not in the moral sense, but in the sense of 

acting to maximize singular objectives, as in a greedy algorithm) is at the core of 

the  neoclassical  economy.  Economists  such  as  Adam  Smith,  in  the  eighteenth 

century, theorized that the individual’s pursuit of self-interest (without a global 

vision or purpose) benefits society as a whole greatly and renders it prosperous in 

economy  (it’s  the  theory  of  the  invisible  hand: 

https://plus.maths.org/

content/adam-smith-and-invisible-hand

).

Detailing how a greedy algorithm works (and under what conditions it can work 

correctly) is straightforward, as explained in the following four steps:

1. 

You can divide the problem into partial problems. The sum (or other combina-

tion) of these partial problems provides the right solution. In this sense, a 

greedy algorithm isn’t much different from a divide-and-conquer algorithm 

(like Quicksort or Mergesort, both of which appear in Chapter 7).

2. 

The successful execution of the algorithm depends on the successful execution 

of every partial step. This is the optimal substructure characteristic because an 

optimal solution is made only of optimal subsolutions.

3. 

To achieve success at each step, the algorithm considers the input data only at 

that step. That is, situation status (previous decisions) determines the decision 

the algorithm makes, but the algorithm doesn’t consider consequences. This 

complete lack of a global strategy is the greedy choice property because being 

greedy at every phase is enough to offer ultimate success. As an analogy, it’s 

akin to playing the game of chess by not looking ahead more than one move, 

and yet winning the game.

4. 

Because the greedy choice property provides hope for success, a greedy 

algorithm lacks a complex decision rule because it needs, at worst, to consider 

all the available input elements at each phase. There is no need to compute 

possible decision implications; consequently, the computational complexity is 

at worst linear O(n). Greedy algorithms shine because they take the simple 

route to solving highly complex problems that other algorithms take forever to 

compute because they look too deep.