What is the running time of conactination on character strings. i.e.
.>>>joe="123" .>>>joe+="99999999999999999"
is it Amortized Constant time? I don't think it would be O((number of chars)^2) but i really don't know.
First of all, this idiom is generally avoided in loops (where it actually matters). Use ''.join() which the documentation describes as optimized for your case and as preferable over creating a larger number of immutable strings. Note that it does not specify the run-time complexity there.
That said, Python is a dynamic, high-level language. CPython is an implementation. IronPython and Jython are different implementations. There are others. Many of the internal complexities are implementation specific. Some have good reasons for this. Also, IronPython and Jython heavily rely on the performance of the underlying run-time environment for their own performance. The differences between the various implementations and their run-time environments can be big enough to render performance specifications useless in many (though possibly not all) cases.
If you need to know the exact complexity of algorithms, read them. Download the source distribution of the Python version you want to investigate and read the source. But remember that there is no actual specification. Do not expect your code to run at the same speed in all Python versions and implementations.
There are examples for basic algorithms that were exchanged during the long evolution of the CPython implementation. One is the sort algorithm. Recent 2.4 changes in the handling of lists made some common operations considerably faster.
It is a pragmatically sane approach to accept the high programming level of Python and to not rely on the specific performance of a specific implementation. Just use the tool that is made for your task. The information for choosing the right tool can already be found in the documentation.
Stefan -- http://mail.python.org/mailman/listinfo/python-list
