Sleep Sort

First, note that the algorithm is hardware-dependent, because forking a new process is not an instantaneous operation, and switching between running threads also takes time. In fact, if there are enough elements in the array so that forking a new process takes more than $\frac{1}{n}$ seconds, the algorithm fails; consider the sequence $1, 0, 0, \ldots, 0$ , where the process printing 1 will finish before the last process printing 0 starts. So now assume that forking a new process takes a very short time, say $\epsilon < \frac{1}{n}$ seconds, and that all threads can run simultaneously without any impact on time (say they are running on parallel processors). We'll also consider that the sequence consists of non-negative integers only, because we don't want to deal with time travel involving sleeping for -1 seconds. (We can generalize this so that the sequence consists of multiples of a certain number $\tau$ ; we then need $\epsilon < \frac{\tau}{n}$ . We cannot have unrestricted rational or real numbers because they might be separated by less than $\epsilon$ .)

Consider the sequence $a_1, a_2, \ldots, a_n$ . The first element takes $\epsilon$ seconds to fork, plus $a_1$ seconds to wait. The second element takes $2\epsilon$ seconds to fork (it needs to wait for the first element to finish forking first), plus $a_2$ seconds to wait. In general, the $i$ -th element takes $i\epsilon$ seconds to fork, plus $a_i$ seconds to wait. Since all elements are running simultaneously, the time taken will be the maximum among these: $\max (i\epsilon + a_i)$ . Because $\epsilon < \frac{1}{n}$ , we have $i\epsilon < 1$ , thus a larger $a_i$ will definitely take more time than a smaller $a_i$ . Among those with the largest $a_i$ , those with larger $i$ will take more time (because $i\epsilon$ is larger when $i$ is larger). Thus suppose the maximum $a_i$ is achieved by $a_k$ (and if tied, take the largest $k$ ). The running time is $k\epsilon + a_k$ seconds.

Thus $k\epsilon + a_k = O(n) + O(\max a_i) = O(\max a_i + n)$ .

The answer is not $O(\max a_i)$ because it's possible to have $a_i = 0$ for all $i$ . In this case, $\max a_i = 0$ , so by definition of big O notation, there should be some $c$ satisfying $k\epsilon + a_k \le c \cdot \max a_i$ , or $k\epsilon \le c \cdot 0 = 0$ , contradiction. If the input is restricted to positive integers only, then the answer $O(\max a_i)$ is more accurate (we can pick $c = 2$ ).