Douglas Gregor wrote: < glossing over the fact complexity is untestable... >
Even if we did, it's unclear how useful it would be except as documentation. We couldn't verify the complexity (except in very simple cases), and it's unlikely to help in program testing or optimization.
It might be useful where there were known ways of combining big-O functions for generic code to flag up "Whoa! don't go there, we exceeded some sanity limit!" For instance, O(n) implementation calls another O(n) function, we 'know' we are dealing with an O(n^2) function. I don't imagine any work on this kind of semantic outside accedemia, but could see some application in a decade or so once someone figures out how to do this simply and reliably, and for once Concepts is probably not that answer ;?) -- AlisdairM