Yes, I was asking where to put the disclaimer.  The thread docs would be approriate if there is nothing already.

Guido has been very reluctant to put any performance guarantees in the language reference.  I believe he said that O(f(n)) info even for CPython should be in the wiki -- and taken as a guideline, not a iron guarantee.

Further discussion might be better directed to python-ideas, after a search of the pydev and python-ideas archives (most easily done with the gmane mirrors, I believe).