Big O Notation

2 years ago | CS Theory Videos
Understanding Big O has many real world benefits, aside from passing a technical interview. In this post I'll provide a cheat sheet and some real world examples.
***

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)

Learn The Core CS Concepts Every Programmer Should Know - Free

In this free, 52 page PDF I'll share with you some of the skills and techniques I use on a daily basis.

We respect your privacy. Unsubscribe at any time.

There's More...

👻 Hacking Ghost for Fun and Profit

I've been using Ghost for many years and recently I decided to see just how far I could push it.

All Courses Are Belong To You

Lots happening here, so here’s an update.

Surviving the Structured Interview

The tech industry is slowly changing over to structured interviews, but most people don't know what they are and that they have a formula!