<p>Chazelle, Liu, and Magen's paper <a href="http://www.cs.princeton.edu/~chazelle/pubs/sublinearSIAM.pdf">Sublinear Geometric Algorithms</a> (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 [<a href="http://www.inf.ethz.ch/personal/gaertner/texts/own_work/sampling.pdf">DCG 2001</a>], who cite the first edition of CLR (1990).</p>

<p>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 </p>

<ul>
<li>$Key[1..n]$ stores a set of $n$ numbers in <strong><em>arbitrary</em></strong> order;</li>
<li>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]$.</li>
</ul>

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

<ul>
<li><p>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$).</p></li>
<li><p>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$).</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2012-03-22T09:11:33.173Z
2012-03-22T09:48:11.830Z
2012-03-22T09:48:11.830Z
Jeffε
<p>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 <a href="http://perso.ens-lyon.fr/eric.thierry/Graphes2009/ir77.pdf">Itai and Rodeh (STOC 1977)</a> 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.</p>

CC BY-SA 3.0
2012-03-21T23:16:28.770Z
2012-03-23T06:17:21.123Z
2012-03-23T06:17:21.123Z
David Eppstein
<p>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</p>

<ul>
<li>baby-step giant-step algorithm for computing discrete logarithm in $O(\sqrt n)$,</li>
<li>static 2D orthogonal range counting in $O(\sqrt n)$ time and $O(n)$ memory,</li>
<li>priority queue with EXTRACT-MIN in $O(\sqrt[k] n)$ and DECREASE-KEY in $O(1)$, </li>
<li>colouring a 3-colourable graph with $O(\sqrt n)$ colours in polynomial time,</li>
</ul>

<p>just to name a few.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-21T16:27:34.740Z
I'm sorry if the question is a bit vague; feel free to improve.
Dmytro Korduban
CC BY-SA 3.0
2012-03-21T16:41:39.177Z
Should this be CW ?
Suresh Venkat
CC BY-SA 3.0
2012-03-21T16:51:11.340Z
@Suresh: If the “big-list ⇒ CW” rule is still in effect, then yes, it should be CW.
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-21T17:01:35.067Z
[Fast matching in unweighted bipartite graphs](http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm) is another good example.
aelguindy
CC BY-SA 3.0
2012-03-22T02:55:00.417Z
it's a basic trick all over the recent algorithms for map reduce models
Sasho Nikolov
CC BY-SA 3.0
2012-03-22T08:28:36.857Z
@SureshVenkat Could you please convert it to the CW then? I can't find a way to do that.
Dmytro Korduban
<ds.algorithms><ds.data-structures><big-list><teaching>
Notable examples of the square root idea in complexity analysis
Dmytro Korduban
# Notable examples of the square root idea in complexity analysis

(Asked by: username_0 on 2012-03-21)

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.

**Tags:** ds.algorithms, ds.data-structures, big-list, teaching
> **Comments:**
> **username_0**: I'm sorry if the question is a bit vague; feel free to improve.  
> **username_1**: Should this be CW ?  
> **username_2**: @Suresh: If the “big-list ⇒ CW” rule is still in effect, then yes, it should be CW.  
> **username_3**: [Fast matching in unweighted bipartite graphs](http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm) is another good example.  
> **username_4**: it's a basic trick all over the recent algorithms for map reduce models  
> **username_0**: @SureshVenkat Could you please convert it to the CW then? I can't find a way to do that.  

---

## 2 answers

### Answer by username_5 on 2012-03-22. Score: 10

Chazelle, Liu, and Magen's paper [Sublinear Geometric Algorithms](http://www.cs.princeton.edu/~chazelle/pubs/sublinearSIAM.pdf) (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](http://www.inf.ethz.ch/personal/gaertner/texts/own_work/sampling.pdf)], 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 by username_6 on 2012-03-21. Score: 10

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)](http://perso.ens-lyon.fr/eric.thierry/Graphes2009/ir77.pdf) 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.


---

