3
$\begingroup$

You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false otherwise). You have access to an unlimited supply of random bits. Consider the following two tasks:

  1. The array is currently sorted. Your algorithm should produce a uniformly (or approximately uniformly) randomly selected permutation.
  2. The array consists of some permutation (uniformly chosen by nature). Your algorithm should sort the array.

My question is:

Which task requires more "energy" asymptotically?

I am unable to define the question more clearly because I don't know enough about the connection between information-theoretic entropy and energy required for a computer operation. So I was hoping that an answer could clarify this connection. But I can think of two approaches to answering the question.

First, an algorithmic one: A comparison-based sort requires $n \log n$ comparisons and about $n$ "swaps"; a random shuffle should require no comparisons and about $n$ swaps (I think). But how much energy do these operations require?

Second, an information-theoretic one (which I am hoping to see!). Sorting a shuffled deck seems to require destroying many bits of information (which is costly, right?) whereas shuffling a sorted deck requires simply transferring my incoming random bits into the deck. It seems like the shuffling algorithm is "cheating" by getting access to random bits; can we quantify this?

$\endgroup$
9
  • 1
    $\begingroup$ If you can generate a uniform random integer from $1$ to $k$ with $O(1)$ energy, for $k=2,\dots n$, you can shuffle in $O(n)$ time. You cannot sort less than $O(n\log n)$ without some condition on the values in the set. $\endgroup$ – Thomas Andrews Apr 12 '13 at 22:21
  • $\begingroup$ @ThomasAndrews that seems a bit too strong an assumption; maybe instead we should assume we can generate a random bit in constant time. $\endgroup$ – usul Apr 13 '13 at 0:13
  • $\begingroup$ Random bits are messier - to get a random shuffle, you have to pick a random number from $1$ to $n!$. If you can only pick a random bit, there is no way to uniformly generate a random number from $1$ to $n!$ in $O(1)$ time, or any finite amount of time. Essentially, there is no way in any finite amount of time to ensure that you can generate a uniform random number from $1$ to $3$ if all you know how to do is generate random bits. $\endgroup$ – Thomas Andrews Apr 13 '13 at 0:22
  • $\begingroup$ @ThomasAndrews good point, and this sort of question is why I added the parenthetical (approximately uniform) permutation. $\endgroup$ – usul Apr 13 '13 at 2:35
  • 1
    $\begingroup$ The question received a (nice) answer here: cs.stackexchange.com/questions/11299/… $\endgroup$ – usul Feb 4 '16 at 5:56