https://twitter.com/puffnfresh/status/307868744401694720
No, still not interesting. :) If your test says code must be O(n), and there is no code, then the test fails (the code does not have that property). If the first test written is "must be O(n)", you could pass this with id.
AFAICT TDD is not about specification* or correctness. It is a mental tool (in the same way a TODO list is a mental tool) for aiding focus, encouraging small steps (divide and conquer) and making steady, incremental progress. Identify a difficiency in what you are currently working on, come up with a test that describes this difficiency (RED), implement just enough to pass that test (GREEN), then see if you can express that in a cleaner way while keeping the test passing (REFACTOR).
This doesn't have to be code-specific, you could use this approach to write a book**. Tests could be tasks on a TODO list, a type signature, an automated unit test, acceptance tests, property test, or whatever. It is just a tool to aid thinking that people can use or not use as they find useful.
(*) although if you have used TDD for an entire project, then all the tests created will be a specification of all the properties it needs to have to be called complete? (complete, not necessarily correct)
(**) I have vague recollections of reading a book that claimed to be written in this manner. Maybe Kent Beck's TDD by example, or James Newkirk's TDD in MS.NET?
The notation O(n) already does mean "or better", although it seems a very common confusion, to say big-O when one means big-Theta. See http://stackoverflow.com/questions/471199/what-is-the-difference-between-n-and-on.