Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Computational complexity question for math experts
Posted:
Jun 11, 2013 10:52 AM


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/interestingcomputationalcomplexityquestion
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/FisherYates_shuffle#The_modern_algorithm> and other sections such as 'The "insideout" algorithm' and 'Potential sources of bias'.
 jiw



