Post

Sam Rose
@samwho.dev

✨ Big O ✨ Let me take you on a visual introduction to what big O notation is in my new blog post: samwho.dev/big-o. With big O notation you can better understand how algorithms will perform in practice, finding orders of magnitude improvements often with very simple changes to your code.

Matias Klemola
@matiasklemola.com

Great post, as expected! 💯 I wonder about the buildList example, though. The time complexity analysis of the function seems to omit the .join() operation, which makes the big O value either O(n^2+n) or O(2n), right?

Sam Rose
@samwho.dev

Technically yes, but big O only includes the most significant contributor to the function’s growth, and then the smallest variant of it. It’s very confusing. So O(n^2+n) is just O(n^2). The idea is to say “the order of growth is no less than this.” I do sometimes see people being more specific.

0 reposts1 like

Matias Klemola
@matiasklemola.com

Right. I’ve seen examples with multiple components, signalling that an algorithm has multiple expensive operations to it (for example, in a gamedev book). In a case of two linear components, there is no clear winner, I guess?

Sam Rose
@samwho.dev

Yeah, when comparing two algorithms of the same big O you have to use other tools like wall clock time. Big O is one of many tools for describing algorithms :)

Matias Klemola
@matiasklemola.com

I’ll add that O(nm) is used for 2D array based functions (e.g. inner loop). Maybe this is something that warrants a mention, like a footnote (to avoid complicating the meat of the article)?