FTA: "Well, hopefully we almost always want the asymptotically optimal algorithm to solve our problem. You might have noticed that the above code is selection sort - an algorithm with best/worse/average time complexity of O(n^2)."
"Sadly, we can't write a test or a type to satisfy our specification. We need to actually perform some (asymptotic) analysis to derive our code, instead of relying on tests!"
Algorithmic complexity is not measurable by the test code, but its also not measurable by your customers. So why measure it? Instead, write a test for something that your customers do care about: performance perhaps? Its easy to throw a huge array at it and see if its too slow.
"Sadly, we can't write a test or a type to satisfy our specification. We need to actually perform some (asymptotic) analysis to derive our code, instead of relying on tests!"
Algorithmic complexity is not measurable by the test code, but its also not measurable by your customers. So why measure it? Instead, write a test for something that your customers do care about: performance perhaps? Its easy to throw a huge array at it and see if its too slow.