16
$\begingroup$

This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page 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.

Improve this question
$\endgroup$

6 Answers 6

Reset to default
25
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 4
    $\begingroup$ 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? $\endgroup$
    – randomwalker
    Aug 16, 2010 at 21:13
  • 2
    $\begingroup$ 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 :) $\endgroup$
    – Suresh Venkat
    Aug 16, 2010 at 21:25
  • 1
    $\begingroup$ Thanks for the answer. I never knew it was such a big deal. The link provides a good reading. $\endgroup$
    – Tomer Vromen
    Aug 16, 2010 at 22:01
  • 1
    $\begingroup$ Bottom line: always make your model explicit. $\endgroup$
    – Jukka Suomela
    Aug 17, 2010 at 10:06
  • 2
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Aug 30, 2010 at 16:30
19
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice point with the loop. Never noticed that... $\endgroup$
    – Tomer Vromen
    Aug 16, 2010 at 22:00
9
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I suspected that the "naive" algorithm had that implicit k... $\endgroup$
    – Tomer Vromen
    Aug 16, 2010 at 22:02
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Jeffε
    Aug 17, 2010 at 21:25
  • $\begingroup$ @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. $\endgroup$
    – ShreevatsaR
    Aug 17, 2010 at 22:31
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Tomer Vromen
    Aug 17, 2010 at 10:40
  • $\begingroup$ 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. $\endgroup$
    – Dave Doty
    Aug 17, 2010 at 15:13
  • $\begingroup$ 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.... $\endgroup$
    – arnab
    Oct 2, 2010 at 7:40
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.