Grokking Algorithms

EXERCISES
Give the run time for each of these scenarios in terms of Big O.
1.3 
You have a name, and you want to find the person’s phone number 
in the phone book. 
1.4
You have a phone number, and you want to find the person’s name 
in the phone book. (Hint: You’ll have to search through the whole 
book!)
1.5
You want to read the numbers of every person in the phone book.
1.6
You want to read the numbers of just the 
A
s. (This is a tricky one! 
It involves concepts that are covered more in chapter 4. Read the 
answer—you may be surprised!)
The traveling salesperson
You might have read that last section and thought, “There’s no way I’ll 
ever run into an algorithm that takes O(
n
!) time.” Well, let me try to 
prove you wrong! Here’s an example of an algorithm with a really bad 
running time. This is a famous problem in computer science, because 
its growth is appalling and some very smart people think it can’t be 
improved. It’s called the
 traveling salesperson 
problem.
You have a salesperson.

---

Chapter 1
 
 
I
 
 
Introduction to algorithms
18
The salesperson has to go to five cities.
This salesperson, whom I’ll call Opus, wants to hit all five cities while 
traveling the minimum distance. Here’s one way to do that: look
at every possible order in which he could travel to the cities.
He adds up the total distance and then picks the path with the
lowest distance. There are 120 permutations with 5 cities, so it will
take 120 operations to solve the problem for 5 cities. For 6 cities, it
will take 720 operations (there are 720 permutations). For 7 cities,
it will take 5,040 operations!