Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


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

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: 358
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 http://www.analyticbridge.com/profiles/blogs/interesting-computational-complexity-question


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
<http://en.wikipedia.org/wiki/Fisher-Yates_shuffle#The_modern_algorithm>
and other sections such as 'The "inside-out" algorithm' and 'Potential
sources of bias'.

--
jiw



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

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.