The saltiest and wrongest article about Big O ever

#computerscience #webdev #rant #funny

Sigh... So you want to learn about Big O Notation huh? Welp, you came to the wrong place, but stay for the ride AS YOU WALK INTO MY RANT ABOUT THIS THING FOR 20 PARAGRAPHS! YES, I'M SCREAMING.

Nobody talks like that

Ok. Maybe some people do, but it is VERY specific and rare. What am I talking about? Look at this function:

function foo(list) {
  const foo = [];

  list.forEach(item => item.bars.forEach(bar => foo.push(bar)));

  return foo;
}

If you just thought "Oh, that is an O(n^2)" then you are a Big O pervert. Sorry. I don't make the rules.

In 15 years of web development, nobody ever reached out to me and talked in Big O terms. People would reach out to me and say "Yeah, that function is doing a nested loop. Maybe we can figure out a way of not doing it", like decent people.

But hey, Big O is not that bad, and there might be scenarios where you need to talk like that. Like, when doing interviews. So when an interviewer asks you "What is the complexity of the function?" you know how to answer, and then proceed to never use it ever again. Or when you need to prove to the C-suite that an optimization needs to happen, so you present some calculations, which they don't understand but nod either way, and they might approve it if there is some lingering "let's make devs happy" budget.

With all that said... That is not a problem with Big O itself. That is just how it is used in the industry. I think that understanding Big O is actually helpful. You can think more about how a function can become a bottleneck pretty easily by thinking how bad does it scale to infinity. Talking about that...

Infinites can be bigger than others, but why care?

THEY CAN, OK?! Some of them are almost the same, but others? They are entirely different beasts. Let's look at these two functions:

function badFoo(list) {
  const bar = [];
  const bibar = [];
  const tribar = [];

  list.forEach((item) => { bar.push(item) });
  list.forEach((item) => { bibar.push(item) });
  list.forEach((item) => { tribar.push(item) });

  return { bar, bibar, tribar };
}

function goodFoo(list) {
  const bar = [];
  const bibar = [];
  const tribar = [];

  list.forEach((item) => {
    bar.push(item);
    bibar.push(item);
    tribar.push(item);
  });

  return { bar, bibar, tribar };
}

Both functions are O(n). One of them is obviously way worse than the other. It should be an O(3n). It actually is that, but if you present that as is someone will pop up saying "Um... Actually. While that is technically correct, you need to drop that constant as it is not a factor that depends on the n. We are only interested in how the function scales to infinity."

You know what? This is what we are doing. It is a WAY bigger growth rate than just O(n). Which leads to a bigger infinite. I would understand if we were talking about sums, but multiplications?

Look at the chart below:

We can see that the Green line is worse than the Red, but it is basically following the same growth path. But take a look at the Black line there. That thing is getting farther and farther as the number of items grow. And how are all of them described? O(n).

I'm tired

Look, this all probably makes sense to a lot of people and it is correct and all. It comes from math and it has been used for many generations. The objective is to look for the part of the function that actually grows the fastest to infinity. Big O notation is just trying to simplify and highlight the issue.

That said, fuck you Big O, Theta, Omega, and the rest of your family as well. Nobody will come to your funeral.