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.

nice post! i love the interactive graphs. there are a few things aren't correct here though. this is false. it's a common misconception, but it's still wrong. O and Θ can both be used to describe worst-case or average case complexities.

the difference is that O is an upper bound (so e.g. n ∈ O(n^2)), whereas Θ is an upper *and lower* bound (f ∈ Θ(g) means f ∈ O(g) *and* g ∈ O(f)) in fact, you used O notation yourself to describe the *expected* complexity of hash sets! (the worst-case complexity is linear)

this is another misconception. O(1) complexity only means that a function is *bounded* by a constant. it can still vary in fact, if you have a time complexity like T(n) = Σ_(i=1)^n (1/2)^i then T is strictly monotonically increasing, but it is still in O(1), because it will never exceed 2.