Andrei Alexandrescu: > (I also have a cool > idea for statistically checking sortedness without deteriorating > complexity. Essentially assumeSorted(r) could check that r is sorted by > tossing a rigged coin with P(head)=1.0/r.length and deciding to check if > head comes up. That way, the amortized complexity of the check is O(1)).
But the safety (reliability) of such test is low, and it can increase a lot the variance of the running time of a piece of code... So it's a cute idea, but I am not sure it's a good one. Bye, bearophile
