Head First Algorithms and Data Structures

Chapter 2. The Universal Language of Algorithm Performance: Big O

A Note for Early Release Readers

With Early Release ebooks, you get books in their earliest form—the author’s raw and unedited content as they write—so you can take advantage of these technologies long before the official release of these titles.

This will be the 2nd chapter of the final book.

If you’d like to be actively involved in reviewing and commenting on this draft, please reach out to the editor at [e-mail].

Your search is fast now. But the real question is, will it stay fast as the input data doubles? Or triples? Or grows to a million?

One way that helps us think about this is the algorithms’ growth curve. Some seem to climb gently, while others explode upward. But how do we actually talk about those curves? We need a vocabulary. How do we describe the difference between an algorithm that scales well as input grows, and one that gets you into trouble?

That’s where Big O comes in. Big O doesn’t care about your processor or your RAM. It cares about how your algorithm behaves, especially when your algorithm is under pressure.

In this chapter, we’ll get comfortable with Big O: how to read it, how to write it, and (yes) how to actually understand it. You won’t need to understand dense formulas (just the opposite) and no math degree is required.

The payoff? Learning how to describe the efficiency ...