Big O: How Many Steps Relative to N Elements?

Big O achieves consistency by focusing on the number of steps an algorithm takes, but in a specific way. Let’s start off by applying Big O to the algorithm of linear search.

In a worst-case scenario, linear search will take as many steps as there are elements in the array. As we’ve previously phrased it: for N elements in the array, linear search can take up to N steps. The appropriate way to express this in Big O notation is:

O(N)

Some pronounce this as “Big Oh of N.” Others call it “Order of N.” My personal preference, however, is “Oh of N.”

Here’s what the notation means. It expresses the answer to what we’ll call the key question. The key question is this: if there are N data elements, how many steps will the algorithm take? Go ahead and read that sentence again. Then, emblazon it on your forehead, as this is the definition of Big O notation that we’ll be using throughout the rest of this book.

The answer to the key question lies within the parentheses of our Big O expression. O(N) says that the answer to the key question is that the algorithm will take N steps.

Let’s quickly review the thought process for expressing time complexity with Big O notation, again using the example of linear search. First, we ask the key question: if there are N data elements in an array, how many steps will linear search take? Because the answer to this question is that linear search will take N steps, we express this as O(N). For the record, an algorithm that is O(N) is also known as having linear time.

Let’s contrast this with how Big O would express the efficiency of reading from a standard array. As you learned in Chapter 1, , reading from an array takes just one step, no matter how large the array is. To figure out how to express this in Big O terms, we’re going to again ask the key question: if there are N data elements, how many steps will reading from an array take? The answer is that reading takes just one step. So we express this as O(1), which I pronounce “Oh of 1.”

O(1) is interesting, since although our key question revolves around N (“If there are N data elements, how many steps will the algorithm take?”), the answer has nothing to do with N. And that’s actually the whole point: no matter how many elements an array has, reading from the array always takes one step.

And this is why O(1) is considered the “fastest” kind of algorithm. Even as the data increases, an O(1) algorithm doesn’t take any additional steps. The algorithm always takes a constant number of steps no matter what N is. In fact, an O(1) algorithm can also be referred to as having constant time.