Ignoring Constants

But here’s the funny thing: in the world of Big O notation, Selection Sort and Bubble Sort are described in exactly the same way.

Again, Big O notation answers the key question: if there are N data elements, how many steps will the algorithm take? Because Selection Sort takes roughly half of N² steps, it would seem reasonable that we’d describe the efficiency of Selection Sort as being O(N² / 2). That is, for N data elements, there are N² / 2 steps. The following table bears this out:

In reality, however, Selection Sort is described in Big O as O(N²), just like Bubble Sort. This is because of a major rule of Big O that I’m now introducing for the first time:

Big O notation ignores constants.

This is simply a mathematical way of saying that Big O notation never includes regular numbers that aren’t an exponent. We simply drop these regular numbers from the expression.

In our case, then, even though the algorithm takes N² / 2 steps, we drop the “/ 2” because it’s a regular number and express the efficiency as O(N²).

Here are a few more examples:

For an algorithm that takes N / 2 steps, we’d call it O(N).

An algorithm that takes N² + 10 steps would be expressed as O(N²) since we drop the 10, which is a regular number.

With an algorithm that takes 2N steps (meaning N * 2), we drop the regular number and call it O(N).

Even O(100N), which is 100 times slower than O(N), is also referred to as O(N).

Offhand, it would seem that this rule would render Big O notation entirely useless, as you can have two algorithms that are described in exactly the same way with Big O, and yet one can be 100 times faster than the other. And that’s exactly what we’re seeing here with Selection Sort and Bubble Sort. Both are described in Big O as O(N²), but Selection Sort is twice as fast as Bubble Sort.

So, what gives?