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

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.

Chazelle, Liu, and Magen's paper Sublinear Geometric Algorithms (STOC 2003, SICOMP 2006) has several clever applications of the following random sampling trick. (“Although we could not find a reference, the following algorithm is probably folklore.”)

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

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