# 1 introduction to algorithms

## Binary search

Binary search is an algorithm; its input is a **sorted list** of elements



example



## Algorithm running times grow at different rates





## Big O establishes a worst-case run time

Q: Suppose you’re using simple search to look for a person in the phone book. In this case, you’re looking for Adit. This guy is the first entry in your phone book. So you didn’t have to look at every entry—you found it on the first try. Did this algorithm take O(n) time? Or did it take O(1) time because you found the person on the first try?

Q: `O(n + 26)`, `O(n - 26)`, `O(n * 26)`, `O(n / 26)`. Which is the fastest?

## The traveling salesperson



There are 120 permutations with 5 cities, so it will take 120 operations to solve the problem for 5 cities.

it's `O(n!)`



The best we can do is come up with an approximate solution; see chapter 10 for more.