robconery.com

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:


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 Subtle Arts of Logging and Testing

    I'm a big fan of testing, but I get lazy sometimes and it ends up costing me money, directly.

    Test-driven Development In Action

    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.

    Meet Playwright

    Curious about Playwright, the frontend testing framework? Well hang out for the next hour and I'll show it to you!