A Common-Sense Guide to Data Structures and Algorithms

Chapter 3Oh Yes! Big O Notation

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

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 that an algorithm takes cannot be pinned down to a single number. Let’s take linear search, for example. The number of steps that linear search takes varies, as it takes as many steps as there are cells in the array. If the array contains twenty-two elements, linear search takes twenty-two steps. If the array has 400 elements, however, linear search takes 400 steps.

The more accurate way to quantify efficiency of linear search is to say ...