1 Introduction to algorithms


In this chapter

  • You get a foundation for the rest of the book.
  • You write your first search algorithm (binary search).
  • You learn how to talk about the running time of an algorithm (big O notation).

An algorithm is a set of instructions for accomplishing a task. Every piece of code could be called an algorithm, but this book covers the more interesting bits. I chose the algorithms in this book for inclusion because they’re fast, or they solve interesting problems, or both. Here are some highlights:

  • Chapter 1 talks about binary search and shows how an algorithm can speed up your code. In one example, the number of steps needed goes from 4 billion down to 32!
  • A GPS device uses graph algorithms (as you’ll learn in chapters 6 and 9) to calculate the shortest route to your destination.
  • You can use dynamic programming (discussed in chapter 11) to write an AI algorithm that plays checkers.

In each case, I’ll describe the algorithm and give you an example. Then I’ll talk about the running time of the algorithm in big O notation. Finally, I’ll explore what other types of problems could be solved by the same algorithm.

What you’ll learn about performance

What you’ll learn about solving problems

Binary search

A better way to search

Running time

Big O notation

Algorithm running times grow at different rates

Visualizing different big O run times

Big O establishes a worst-case run time

Some common big O run times

The traveling salesperson