On Mon, Apr 15, 2013 at 11:14 AM, Steven D'Aprano <steve+comp.lang.pyt...@pearwood.info> wrote: > On Sun, 14 Apr 2013 17:44:28 -0700, Mark Janssen wrote: >> What on earth makes you think that is an O(n**2) algorithm and not O(n)? > > Python *might* optimize the first concatenation, '' + 'fe', to just reuse > 'fe', (but it might not). Let's assume it does, so that no copying is > needed. Then it gets to the second concatenation, and now it has to copy > characters, because strings are immutable and cannot be modified in > place.
There are actually a lot of optimizations done, so it might turn out to be O(n) in practice. But strictly in the Python code, yes, this is definitely O(n*n). ChrisA -- http://mail.python.org/mailman/listinfo/python-list
