Start Here: The Best-Imaginable Big O

While all the techniques in this chapter are useful, you’ll find that some come in handy for certain scenarios, while others are effective for other scenarios.

This first technique, however, applies to all algorithms and should be the first step of your optimization process.

And here it is.

Once you’ve determined the efficiency of your current algorithm (the prereq), come up with what you believe to be what I call the “best-imaginable Big O.” (I’ve seen others refer to this as the “best-conceivable runtime” when applied to speed.)

Essentially, the best-imaginable Big O is the absolute best Big O you could dream of for the problem at hand. This is the Big O you know is absolutely impossible to beat.

For example, if we were to write a function that prints every item from an array, we’d probably say that the best-imaginable Big O for this task is O(N). Given that we have to print each of the N items in the array, we have no choice but to process each of the N items. There’s no way around this fact, as we need to “touch” each item to print it. Because of this, O(N) is the best-imaginable Big O we could imagine for this scenario.

When optimizing an algorithm, then, we need to determine two Big Os. We need to know the Big O our algorithm currently takes (the prereq), and we need to come up with the best-imaginable Big O the task could possibly take.

If these two Big Os are not the same, it means we have something to optimize. If, say, my current algorithm has a runtime of O(N²), but the best-imaginable Big O is O(N), we now have an improvement to strive for. The gap between the two Big Os shows us the potential gains we can make through optimization.

Let’s summarize these steps:

Determine the Big O category of your current algorithm. (This is the prereq.)
Determine the best-imaginable Big O you could dream of for the problem at hand.
If the best-imaginable Big O is faster than your current Big O, you can now try to optimize your code, with the goal of bringing your algorithm as close to the best-imaginable Big O as possible.

It’s important to stress that it’s not always possible to achieve the best-imaginable Big O. After all, just because you can dream of something doesn’t mean it can become reality.

In fact, it might turn out that your current implementation cannot be optimized further. However, the best-imaginable Big O is still a tool for giving us a goal to shoot for with our optimization.

Often, I find that I can successfully optimize an algorithm to a speed that is in between my current Big O and the best-imaginable Big O.

For example, if my current implementation is O(N²), and my best-imaginable Big O is O(log N), I’ll aim to optimize my algorithm to become O(log N). If, in the end, my optimizations speed up my code to “just” O(N), that’s still a great success, and the best-imaginable Big O will have served a useful purpose.

Stretching the Imagination

As you’ve seen, the benefit of coming up with the best-imaginable Big O is that it gives us an optimization goal to shoot for. To really make the most of this, it’s worth stretching the imagination a bit to come up with a best-imaginable Big O that is amazing. In fact, I recommend making your best-imaginable Big O the fastest Big O you can think of that isn’t outright impossible.

Here’s another mental trick I use for stoking my imagination. I pick a really fast Big O for the problem at hand—let’s call it “Amazing Big O.” I then ask myself, “If someone told me that they know how to pull off the Amazing Big O for this problem, would I believe them?” If I’d believe someone who said that they figured out how to solve this problem with the efficiency of Amazing Big O, I then make the Amazing Big O my best-imaginable Big O.

Once we know the Big O of our current algorithm and the best-imaginable Big O that we’re aiming for, we’re primed for optimization.

In the remainder of this chapter, we are going to explore additional optimization techniques and mental strategies that can help us boost the efficiency of our code.