Just launched! Get 30% off The Imposter's Frontend Accelerator Get It Now

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...

    The Imposter's Frontend Accelerator

    JavaScript client frameworks are powerful and help you create an amazing experience for your end user. Unfortunately, learning how to use them sucks.

    🤖 A Real World Approach to Playwright

    Writing tests can be tricky, especially using a more complex tool like Playwright. I took some time and dug in over the last year and I'm happy I did.

    What Is Your Yeet Threshold?

    Solving problems is what we do, but sometimes the solution is to burn it all down and start again, learning from your mistakes. How do you make this choice?