There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples includebaby-step giant-step algorithm for computing discrete logarithm in $O(\sqrt n)$,static 2D orthogonal range counting in $O(\sqrt n)$ time and $O(n)$ memory,priority queue with EXTRACT-MIN in $O(\sqrt[k] n)$ and DECREASE-KEY in $O(1)$, colouring a 3-colourable graph with $O(\sqrt n)$ colours in polynomial time,just to name a few.While such algorithms often are suboptimal, they are easy to understand by students and good to quickly show that naive bounds aren't optimal. Also, square-root-idea data structures are sometimes more practical than their binary tree based counterparts because of cache friendliness (not considering cache-oblivious techniques). That's why I give a nice bit of attention to this topic while teaching.I'm interested in more distinctive examples of this kind. So I'm looking for any (preferably elegant) algorithms, data structures, communication protocols etc which analysis relies on the square root idea. Their asymptotics do not need to be optimal.
Notable examples of the square root idea in complexity analysis
ds.algorithms;ds.data structures;big list;teaching