Notable examples of the square root idea in complexity analysis

Question

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 include

• baby-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.

Answer 1

Chazelle, Liu, and Magen's paper Sublinear Geometric Algorithms (STOC 2003, SICOMP 2006) has several clever applications of the following random sampling trick. Variations of the same trick were previously used by Gärtner and Welzl [DCG 2001], who cite the first edition of CLR (1990).

Suppose we are given a sorted circular linked list of numbers, stored in a contiguous block of memory. That is, we have two arrays $Key[1..n]$ and $Next[1..n]$, where

• $Key[1..n]$ stores a set of $n$ numbers in arbitrary order;
• If $Key[i]$ is the largest number in the set, then $Key[Next[i]]$ is the smallest number in the set; otherwise, $Key[Next[i]]$ is the smallest number in the set that is larger than $Key[i]$.

Then we can find the successor of a given number $x$ in $O(\sqrt{n})$ expected time as follows:

• Choose a random sample of $\sqrt{n}$ elements of the array $Key$. Let $Key[j]$ be the largest sample that is smaller than $x$ (or the largest sample, if all samples are greater than $x$).

• Follow $Next$ pointers from $Key[j]$ until we see a number greater than or equal to $x$ (after wrapping around if all samples were larger than $x$).

A relatively simple application of Yao's lemma implies that the $O(\sqrt{n})$ expected time bound is optimal. Any deterministic algorithm for this problem requires $\Omega(n)$ time in the worst case.

Answer 2

There are $O(m^{3/2})$ triangles in any $m$-edge graph and that they can be found in $O(m^{3/2})$ time. There are many ways of doing this but I think one of the earliest is Itai and Rodeh (STOC 1977) who provide an algorithm that goes through a sequence of linear-time iterations, each of which removes a spanning forest from the graph. In the early iterations when the remaining forest has at least $n-k$ components, the algorithm removes at least $k$ edges per step, and in the late iterations when it has at most $n-k$ components, the maximum degree is $k$ and shrinks by at least one in each step. So the total number of iterations is at most $m/k+k$ and choosing the right tradeoff gives the overall bound of $O(\sqrt m)$ on iterations and $O(m^{3/2})$ on time.