A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

The Soul of Big O

Now that we’ve encountered O(N) and O(1), we begin to see that Big O Notation does more than simply describe the number of steps an algorithm takes, such as with a hard number like 22 or 400. Rather, it’s an answer to that key question on your forehead: if there are N data elements, how many steps will the algorithm take?

While that key question is indeed the strict definition of Big O, there’s actually more to Big O than meets the eye.

Let’s say we have an algorithm that always takes three steps no matter how much data there is. That is, for N elements, the algorithm always takes three steps. How would you express that in terms of Big O?

Based on everything you’ve learned up to this point, you’d probably say that it’s O(3). ...