<p>The standard model of computation assumes that arithmetic operations on O(log n)-bit integers can be executed in constant time, since those operations are typically handed in hardware.  So in the Fisher-Yates algorithm, "writing the integer i in memory" only takes O(1) time.</p>

<p>Of course, it's perfectly meaningful to analyze algorithm in terms of bit operations, but the bit-cost model is less predictive of actual behavior.  Even the simple loop <code>for i = 1 to n: print(i)</code> requires O(n log n) bit operations.</p>

CC BY-SA 2.5
2010-08-16T22:00:26.873Z
Nice point with the loop. Never noticed that...
Tomer Vromen
CC BY-SA 2.5
2010-08-16T21:05:59.067Z
2010-08-16T21:05:59.067Z
Jeffε
<p>This is an answer to "[Fisher-Yates algorithm] isn't better than the naive algorithm. Am I missing something here?" which you asked in the question.</p>

<p>In your "naive" algorithm which uses real numbers: how many bits of accuracy do you use? If you're counting bit complexity (as you seem to be doing for Fisher-Yates), and the algorithm uses k random bits for the real numbers, then its running time would be Ω(kn log n), since comparing two k-bit real numbers takes Ω(k) time. But k needs to be at least Ω(log n) to prevent two elements being mapped to the same real number, which means that the algorithm takes Ω(n log<sup>2</sup> n) time, which is slower than the Fisher-Yates shuffle by a factor of log n.</p>

<p>If you're just counting the <em>number</em> of arithmetic and comparison operations and ignoring their bit complexity, then Fisher-Yates is &Theta;(n) and your algorithm is &Theta;(n log n), still a factor of log n apart.</p>

CC BY-SA 2.5
2010-08-16T22:02:50.960Z
I suspected that the "naive" algorithm had that implicit k...
Tomer Vromen
CC BY-SA 2.5
2010-08-17T21:25:15.123Z
The "naive" algorithm can be implemented cleanly in linear time as follows.  Assign each element a random integer between 1 and n^3, and then sort the numbers in O(n) time via radix sort.  (With high probability, no two elements will get the same random number.  If there are duplicates, reshuffle them recursively.)
Jeffε
CC BY-SA 2.5
2010-08-17T22:31:13.593Z
@JeffE: Thanks! That's very clean, and has the same complexity as Fisher-Yates. After posting this, I was actually feeling that the “naive” algorithm shouldn't be worse... I missed the fact that n k-bit numbers can be sorted in O(nk), not needing O(nklog n). But I guess Knuth-Fisher-Yates is still better in the constants: it requires exactly (log n!) random bits—a random integer from 1 to n, then 1 to n-1, etc.—which is optimal (instead of 3n log n), and it can be done in-place with only constant extra memory.
ShreevatsaR
CC BY-SA 2.5
2010-08-16T21:11:08.947Z
2010-08-16T21:24:35.677Z
2010-08-16T21:24:35.677Z
ShreevatsaR
<p>There is nothing special about integers for this problem.</p>

<p>For instance, hash tables (storing any kind of values) are not O(1) time to access if the hash function must read the whole value to compute its hash.  n unique elements require log n bits each on average to represent, no matter how clever your representation, and any hash function that reads its whole input will therefore take at least as much time to compute. In practice they are faster than red-black trees, but asymptotically they are no better.</p>

<p>The brouhaha referenced by randomwalker was about a POPL 2008 paper ( <a href="http://portal.acm.org/citation.cfm?doid=1328438.1328460" rel="noreferrer">http://portal.acm.org/citation.cfm?doid=1328438.1328460</a>), discussed here: <a href="http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html" rel="noreferrer">http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html</a></p>

<p>In that post Lance Fortnow describes how as a student he complained that sorting really requires n log^2 n time if we must read all log n bits of two elements in order to compare them, which seems a reasonable objection.</p>

CC BY-SA 2.5
2010-10-02T07:40:42.787Z
I don't get the O(n log^2 n) objection because in terms of bits, the input itself is of size O(n log n).  Btw, as a side note, the quality level of comments on the complexity blog was so much higher then....
arnab
CC BY-SA 2.5
2010-08-17T10:40:55.293Z
I don't get the author of the blog post. He complains that sorting is actually O(n log^2 n), but then says that the paper is solid?
Tomer Vromen
CC BY-SA 2.5
2010-08-17T15:13:31.663Z
The paper is solid (i.e., not false) in that there is a model in which arithmetic operations take unit time, and in that model the paper's algorithm is the first to achieve o(n^3) operations.
Dave Doty
CC BY-SA 2.5
2010-08-17T03:31:30.170Z
2010-08-17T03:31:30.170Z
Dave Doty
<blockquote>
  <p>The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n).</p>
</blockquote>

<p>Actually, O(n log n) is a lower bound for this problem in models where sorting is O(n log n). If all permutations are equally likely then the algorithm as a function from random streams to permutations must be surjective. There are n! permutations so in something like a decision tree model there are branches of length at least O(log n!) = O(n log n).</p>

<p>This worst-case lower bound still works for non-uniform random generation of permutations so long as all permutations have non-zero probabilities. What changes is the average complexity. It looks like the lower bound on the average complexity in a decision tree model is the entropy of the distribution. With binary decision trees, this lower bound can only be exactly achieved when the distribution is dyadic. The extreme case is when one distinguished permutation has probability $1-\epsilon$ and everything else has equal probability. Then a lower bound on the average complexity should be $O(\epsilon)$.</p>

CC BY-SA 2.5
2010-10-02T07:21:43.370Z
2010-10-02T10:10:03.977Z
2010-10-02T10:10:03.977Z
Per Vognsen
<p>In TCS, we consider -- if not stated otherwise explicitly -- complexity on a Turing Machine. While this is fine for theoretical purposes, results are not very helpful in practice since we do implement different machine models (that is, finite approximations) in hardware. It is therefore a feasible question to ask for complexity on those models. For example, we typically assume that register machines (similar to real CPUs) can perform atomic operations on two registers in constant time -- this is what might have been employed here.</p>

<p>In short: You think in terms of TMs, the article authors in terms of RMs. You are both right.</p>

CC BY-SA 2.5
2010-10-02T11:48:12.490Z
2010-10-02T11:48:12.490Z
Raphael
<p>I suspect that here, like in most algorithms work, the cost of reading and writing $O(\log n)$ bit numbers is assumed to be a constant. It's a minor sin, as long as you don't get carried away and <a href="http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html" rel="noreferrer">collapse P and PSPACE by accident</a>. </p>

CC BY-SA 2.5
2010-08-30T16:30:08.047Z
I think the main reason that we let $O(\log n)$ bit ops be constant time is that (in polynomial time) you can program a constant-time access lookup table for all pairs of $O(\log n)$-bit operands, for most "modern" computational models. There is nothing "sinful" about that... to me, I see this property as one that can simply be assumed without loss of generality.
Ryan Williams
CC BY-SA 2.5
2010-08-30T16:51:13.010Z
log n bit ops are not problematic in and of themselves, that is true. it's forgetting to do the bookkeeping when they grow that's a problem.
Suresh Venkat
CC BY-SA 2.5
2010-11-03T12:17:58.780Z
I meant polynomial time. The lookup table does take polynomial space, in addition.
Ryan Williams
CC BY-SA 2.5
2010-08-16T21:13:23.190Z
While that is indeed a "minor sin," I think it is a major sin of TCS pedagogy that this is never mentioned explicitly! Every single CS student discovers this for themselves, and thinks something major is wrong until they are told that everyone knows this but no one talks about it.

Also, wasn't there a brouhaha a couple of years ago when someone exploited the O(log n) model to give a sub-cubic time algorithm for some famous problem that was conjectured to be Omega(n^3)? Did that ever get resolved?
randomwalker
CC BY-SA 2.5
2010-08-16T21:25:01.153Z
I'm not aware of the brouhaha you're referring to. As for not mentioning it, you're definitely right. After I first read Jeff Erickson's post, I now make it a point to prove P = PSPACE in my geometry class just for kicks :)
Suresh Venkat
CC BY-SA 2.5
2010-08-16T22:01:51.257Z
Thanks for the answer. I never knew it was such a big deal. The link provides a good reading.
Tomer Vromen
CC BY-SA 2.5
2010-08-17T10:06:34.110Z
Bottom line: always make your model explicit.
Jukka Suomela
CC BY-SA 2.5
2010-08-16T21:04:00.307Z
2010-08-16T21:04:00.307Z
Suresh Venkat
<p>This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" rel="noreferrer">Wikipedia page</a> says that its complexity is O(n), but I think that it is O(n log n).</p>

<p>In each iteration i, a random integer is chosen between 1 and i. Simply writing the integer in memory is O(log i), and since there are n iterations, the total is</p>

<p>O(log 1) + O(log 2) + ... + O(log n) = O(n log n)</p>

<p>which isn't better the the naive algorithm. Am I missing something here?</p>

<p>Note: The naive algorithm is to assign each element a random number in the interval (0,1) , then sort the array with regard to the assigned numbers.</p>

<ds.algorithms><permutations>
Complexity of the Fisher-Yates Shuffle Algorithm
Tomer Vromen
# Complexity of the Fisher-Yates Shuffle Algorithm

(Asked by: username_0 on 2010-08-16)

This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The [Wikipedia page](http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) says that its complexity is O(n), but I think that it is O(n log n).

In each iteration i, a random integer is chosen between 1 and i. Simply writing the integer in memory is O(log i), and since there are n iterations, the total is

O(log 1) + O(log 2) + ... + O(log n) = O(n log n)

which isn't better the the naive algorithm. Am I missing something here?

Note: The naive algorithm is to assign each element a random number in the interval (0,1) , then sort the array with regard to the assigned numbers.

**Tags:** ds.algorithms, permutations


---

## 6 answers

### Answer by username_7 on 2010-08-16. Score: 25 | Accepted answer

I suspect that here, like in most algorithms work, the cost of reading and writing $O(\log n)$ bit numbers is assumed to be a constant. It's a minor sin, as long as you don't get carried away and [collapse P and PSPACE by accident](http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html).

> **Comments:**
> **username_9**: While that is indeed a "minor sin," I think it is a major sin of TCS pedagogy that this is never mentioned explicitly! Every single CS student discovers this for themselves, and thinks something major is wrong until they are told that everyone knows this but no one talks about it.  Also, wasn't there a brouhaha a couple of years ago when someone exploited the O(log n) model to give a sub-cubic time algorithm for some famous problem that was conjectured to be Omega(n^3)? Did that ever get resolved?  
> **username_7**: I'm not aware of the brouhaha you're referring to. As for not mentioning it, you're definitely right. After I first read Jeff Erickson's post, I now make it a point to prove P = PSPACE in my geometry class just for kicks :)  
> **username_0**: Thanks for the answer. I never knew it was such a big deal. The link provides a good reading.  
> **username_10**: Bottom line: always make your model explicit.  
> **username_8**: I think the main reason that we let $O(\log n)$ bit ops be constant time is that (in polynomial time) you can program a constant-time access lookup table for all pairs of $O(\log n)$-bit operands, for most "modern" computational models. There is nothing "sinful" about that... to me, I see this property as one that can simply be assumed without loss of generality.  
> **username_7**: log n bit ops are not problematic in and of themselves, that is true. it's forgetting to do the bookkeeping when they grow that's a problem.  
> **username_8**: I meant polynomial time. The lookup table does take polynomial space, in addition.  

---

### Answer by username_1 on 2010-08-16. Score: 19

The standard model of computation assumes that arithmetic operations on O(log n)-bit integers can be executed in constant time, since those operations are typically handed in hardware. So in the Fisher-Yates algorithm, "writing the integer i in memory" only takes O(1) time.

Of course, it's perfectly meaningful to analyze algorithm in terms of bit operations, but the bit-cost model is less predictive of actual behavior. Even the simple loop `for i = 1 to n: print(i)` requires O(n log n) bit operations.

> **Comments:**
> **username_0**: Nice point with the loop. Never noticed that...  

---

### Answer by username_2 on 2010-08-16. Score: 9

This is an answer to "[Fisher-Yates algorithm] isn't better than the naive algorithm. Am I missing something here?" which you asked in the question.

In your "naive" algorithm which uses real numbers: how many bits of accuracy do you use? If you're counting bit complexity (as you seem to be doing for Fisher-Yates), and the algorithm uses k random bits for the real numbers, then its running time would be Ω(kn log n), since comparing two k-bit real numbers takes Ω(k) time. But k needs to be at least Ω(log n) to prevent two elements being mapped to the same real number, which means that the algorithm takes Ω(n log2 n) time, which is slower than the Fisher-Yates shuffle by a factor of log n.

If you're just counting the *number* of arithmetic and comparison operations and ignoring their bit complexity, then Fisher-Yates is Θ(n) and your algorithm is Θ(n log n), still a factor of log n apart.

> **Comments:**
> **username_0**: I suspected that the "naive" algorithm had that implicit k...  
> **username_1**: The "naive" algorithm can be implemented cleanly in linear time as follows.  Assign each element a random integer between 1 and n^3, and then sort the numbers in O(n) time via radix sort.  (With high probability, no two elements will get the same random number.  If there are duplicates, reshuffle them recursively.)  
> **username_2**: @JeffE: Thanks! That's very clean, and has the same complexity as Fisher-Yates. After posting this, I was actually feeling that the “naive” algorithm shouldn't be worse... I missed the fact that n k-bit numbers can be sorted in O(nk), not needing O(nklog n). But I guess Knuth-Fisher-Yates is still better in the constants: it requires exactly (log n!) random bits—a random integer from 1 to n, then 1 to n-1, etc.—which is optimal (instead of 3n log n), and it can be done in-place with only constant extra memory.  

---

### Answer by username_3 on 2010-08-17. Score: 6

There is nothing special about integers for this problem.

For instance, hash tables (storing any kind of values) are not O(1) time to access if the hash function must read the whole value to compute its hash. n unique elements require log n bits each on average to represent, no matter how clever your representation, and any hash function that reads its whole input will therefore take at least as much time to compute. In practice they are faster than red-black trees, but asymptotically they are no better.

The brouhaha referenced by username_9 was about a POPL 2008 paper ( <http://portal.acm.org/citation.cfm?doid=1328438.1328460>), discussed here: <http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html>

In that post Lance Fortnow describes how as a student he complained that sorting really requires n log^2 n time if we must read all log n bits of two elements in order to compare them, which seems a reasonable objection.

> **Comments:**
> **username_0**: I don't get the author of the blog post. He complains that sorting is actually O(n log^2 n), but then says that the paper is solid?  
> **username_3**: The paper is solid (i.e., not false) in that there is a model in which arithmetic operations take unit time, and in that model the paper's algorithm is the first to achieve o(n^3) operations.  
> **username_4**: I don't get the O(n log^2 n) objection because in terms of bits, the input itself is of size O(n log n).  Btw, as a side note, the quality level of comments on the complexity blog was so much higher then....  

---

### Answer by username_5 on 2010-10-02. Score: 4

> The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n).

Actually, O(n log n) is a lower bound for this problem in models where sorting is O(n log n). If all permutations are equally likely then the algorithm as a function from random streams to permutations must be surjective. There are n! permutations so in something like a decision tree model there are branches of length at least O(log n!) = O(n log n).

This worst-case lower bound still works for non-uniform random generation of permutations so long as all permutations have non-zero probabilities. What changes is the average complexity. It looks like the lower bound on the average complexity in a decision tree model is the entropy of the distribution. With binary decision trees, this lower bound can only be exactly achieved when the distribution is dyadic. The extreme case is when one distinguished permutation has probability $1-\epsilon$ and everything else has equal probability. Then a lower bound on the average complexity should be $O(\epsilon)$.


---

### Answer by username_6 on 2010-10-02. Score: 3

In TCS, we consider -- if not stated otherwise explicitly -- complexity on a Turing Machine. While this is fine for theoretical purposes, results are not very helpful in practice since we do implement different machine models (that is, finite approximations) in hardware. It is therefore a feasible question to ask for complexity on those models. For example, we typically assume that register machines (similar to real CPUs) can perform atomic operations on two registers in constant time -- this is what might have been employed here.

In short: You think in terms of TMs, the article authors in terms of RMs. You are both right.


---

