transforming a list into a string

[Roy Smith]

I wrote:
> > The code above runs in O(n).
 
Jp Calderone <exarkun at divmod.com> wrote:
>    Are you sure?  Did you consider the complexity of list.pop(0)?

I'm assuming list.pop() is O(1), i.e. constant time.  Is it not?

Of course, one of my pet peeves about Python is that the complexity of 
the various container operations are not documented.  This leaves users 
needing to guess what they are, based on assumptions of how the 
containers are probably implemented.