The Math Forum

Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Computational complexity question for math experts
Replies: 9   Last Post: Jun 11, 2013 10:52 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
James Waldby

Posts: 545
Registered: 1/27/11
Re: Computational complexity question for math experts
Posted: Jun 11, 2013 10:52 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Mon, 10 Jun 2013 22:02:51 -0700, Vincent Granville wrote:

> It's about an algorithm to generate random permutations, to find the asymptotic distribution of a new metric to measure correlation. The algorithm has a random component. It's O(n log n). Can it be improved? Worst case results in infinite loop.
> Read details at

As I mentioned in reply to your post of 08 Jun 2013 08:49:15 -0700
titled "Conjecture about permutations", the Fisher?Yates shuffle is
an O(n) random permutation generator, vs the O(n ln n) coupon-
collecting method you are asking about. See
and other sections such as 'The "inside-out" algorithm' and 'Potential
sources of bias'.


Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.