Ah but that wouldn't be representative benchmarking. Consider the later example about finding a random word on the large list -- if you fix the random seed and

Ah but that wouldn't be representative benchmarking. Consider the later example about finding a random word on the large list -- if you fix the random seed and that turns out to search for 'aardvark' then the linear search will perform well, but it won't be a good measure of how fast the program is in more general conditions. Your idea works for comparing machines though.