Chapter 3
O Yes! Big O Notation

We’ve seen in the preceding chapters that the primary factor in determining an algorithm’s efficiency is the number of steps it takes.

However, we can’t simply label one algorithm a “22-step algorithm” and another a “400-step algorithm.” This is because the number of steps an algorithm takes cannot be pinned down to a single number. Let’s take linear search, for example. The number of steps linear search takes varies, as it takes as many steps as there are elements in the array. If the array contains 22 elements, linear search takes 22 steps. If the array contains 400 elements, however, linear search takes 400 steps.

The more effective way, then, to quantify the efficiency of linear search is to say that linear search takes N steps for N elements in the array; that is, if an array has N elements, linear search takes N steps. Now, this is a pretty wordy way of expressing this concept.

To help ease communication regarding time complexity, computer scientists have borrowed a concept from the world of mathematics to describe a concise and consistent language around the efficiency of data structures and algorithms. Known as Big O notation, this formalized expression of these concepts allows us to easily categorize the efficiency of a given algorithm and convey it to others.

Once you understand Big O notation, you’ll have the tools to analyze each algorithm going forward in a consistent and concise way—it’s the way the pros do it.

While Big O notation comes from the math world, I’m going to leave out all the mathematical jargon and explain it as it relates to computer science. Additionally, I’m going to begin by explaining Big O notation in simple terms and then continue to refine it as we proceed through this chapter and the next three chapters. It’s not a difficult concept, but it’ll be made even easier if I explain it in chunks over multiple chapters.