Post

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

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?

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.

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?