Comment by teiferer
That's neither random nor O(1). I think everybody reading the link immediately understands what you mean, but I whished this community would use its technical terminology more carefully.
That's neither random nor O(1). I think everybody reading the link immediately understands what you mean, but I whished this community would use its technical terminology more carefully.
I use "random" in quotation marks because it communicates the topic effectively and is very straight to the point. Colloquially, when people say "random" in the context of algorithms, it's generally understood to mean "pseudorandom" or "quasirandom". The trick is essentially an LCG using coprime numbers.
The blog post uses "random" in quotations as well in its title.
I call it O(1) because the ordering is fully determined just by choosing an arbitrary prime number. It's constant time to "reorder" the elements and also constant time to get the i'th element in the permutation. This is in contrast to something like the the Fisher-Yates shuffle which permutes the elements in O(n) time.