how to duplicate array entries  Steven D'Aprano steve at Mon Jan
11 22:58:00 CET 2010  On Mon, 11 Jan 2010 10:03:04 +0100, Alf P.
Steinbach wrote:  >>> A Python "list" is an array functionality-
wise. >>> If one isn't observant of that fact then one ends up
with O(n^2) time >>> for the simplest things. >> Well that's
certainly not true. Some operations may be O(N**2), but >>
others are not: list.append() is amortized O(N) and for
individual >> appends, may be can be as fast as O(1). > The
second sentence may or may not be true. I don't know of any >
fundamental 'list' operations that have quadratic time. Is
there?  I should hope not, but you seem to indicate that there
are, or could be  -- you were the one who made the claim of
O(N**2).  If you're talking about functions someone might write
themselves, well  there is no limit on the awfulness of that. No
doubt you're aware of  Bogosort, which has performance O(N!)
instead of O(N*log N). Or the  (sadly very common) "Polish
Painter Algorithm".   With a bit of wo