> they start with the assumption that every possible ordering is equally likely If the times in each run are independent, this assumption is (for some distribu

> they start with the assumption that every possible ordering is equally likely If the times in each run are independent, this assumption is (for some distributions) the weakest form of "X is not faster than Y." For a distribution where this is not the case: assume - X always runs in 999 seconds, and - Y runs in 1000 seconds in 99% of runs and in 0 seconds the other 1% of the time. Then XXXYYY is a very likely ordering (~97% chance), though Y runs faster than X "on average". (Not in median or mode though.) For a more concrete example: say you have two sorting algorithms, one that is a little slower most of the time, but worst case O(n log n), and another that is usually a bit faster but can be O(n^2) on pathological input.