When I started writing The Imposter’s Handbook, this was the question that was in my head from the start: what the f*** is Big O and why should I care? I remember giving myself a few weeks to jump in and figure it out but, fortunately, I found that it was pretty straightforward after putting a few smaller concepts together.
Big O is conceptual. Many people want to qualify the efficiency of an algorithm based on the number of inputs. A common thought is if I have a list with 1 item it can’t be O(n) because there’s only 1 item so it’s O(1). This is an understandable approach, but Big O is a technical adjective, it’s not a benchmarking system. It’s simply using math to describe the efficiency of what you’ve created.
Big O is worst-case, always. That means that even if you think you’re looking for is the very first thing in the set, Big O doesn’t care, a loop-based find is still considered O(n). That’s because Big O is just a descriptive way of thinking about the code you’ve written, not the inputs expected.
THERE YOU HAVE IT
I find myself thinking about things in terms of Big O a lot. The cart example, above, happened to me just over a month ago and I needed to make sure that I was flexing the power of Redis as much as possible.
I don’t want to turn this into a Redis commercial, but I will say that it (and systems like it) have a lot to offer when you start thinking about things in terms of time complexity, which you should! It’s not premature optimization to think about Big O upfront, it’s programming and I don’t mean to sound snotty about that! If you can clip an O(n) operation down to O(log n) then you should, don’t you think?
So, quick review:
- Plucking an item from a list using an index or a key: O(1)
- Looping over a set of n items: O(n)
- A nested loop over n items: O(n^2)
- A divide and conquer algorithm: O(log n)
I'm a big fan of testing, but I get lazy sometimes and it ends up costing me money, directly.
TDD is one of those things that people talk about, argue about, and think is interesting. I'm one of those people, so I asked Brad Wilson to clear it all up for me.