A Common-Sense Guide to Data Structures and Algorithms

The Role of Big O

Despite the fact that Big O doesn’t distinguish between Bubble Sort and Selection Sort, it is still very important, because it serves as a great way to classify the long-term growth rate of algorithms. That is, for some amount of data, O(N) will be always be faster than O(N²). And this is true no matter whether the O(N) is really O(2N) or even O(100N) under the hood. It is a fact that there is some amount of data at which even O(100N) will become faster than O(N²). (We’ve seen essentially the same concept in Chapter 3, ​Oh Yes! Big O Notation​ when comparing a 100-step algorithm with O(N), but we’ll reiterate it here in our current context.)

Look at the first graph, in which we compare O(N) with O(N²).

We’ve seen this graph ...