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 was on purpose, I wanted to avoid talking about amortisation and figured this little fib wasn’t the end of the world.

oh to be clear: using O is correct here! if you wanted to be 100% exact you would have to write "O(1) expected time complexity", but in this case it's pretty common to leave that inferred.

it's not because of amortization though, it's because hash sets are probabilistic data structures that use randomness to select the hash function. if you knew the hash function you could (theoretically) guess inputs that always cause a collision and degrade lookups to O(n).