# looping versus comprehension

Roy Smith roy at panix.com
Thu Jan 31 09:28:41 CET 2013

```In article <5109fe6b\$0\$11104\$c3e8da3 at news.astraweb.com>,
Steven D'Aprano <steve+comp.lang.python at pearwood.info> wrote:

> On Thu, 31 Jan 2013 02:49:31 +1100, Chris Angelico wrote:
>
> > it's worth
> > noting that list appending is not going to be O(N*N), because it's going
> > to allow room for expansion.
>
> This is true for list.append, which is amortized constant time. But it is
> not true for list addition, alist + blist, which is O(N**2) and hence
> gets really, really slow:
>
> steve at runes:~\$ python -m timeit "L = []" "for i in xrange(1000): L = L + [1]"
> 100 loops, best of 3: 3.08 msec per loop
> steve at runes:~\$ python -m timeit "L = []" "for i in xrange(5000): L = L + [1]"
> 10 loops, best of 3: 71 msec per loop
> steve at runes:~\$ python -m timeit "L = []" "for i in xrange(25000): L = L + [1]"
> 10 loops, best of 3: 2.06 sec per loop
>
>
> Notice that as the number of list additions goes up by a factor of 5,
> the time taken goes up by a factor of 25.

It's not the addition, per-se, that's the problem.  It's the creation of
a new list each time.  If you use +=, it's back to O(n):

~\$ python -m timeit "L = []" "for i in xrange(1000): L += [1]"
1000 loops, best of 3: 275 usec per loop

~\$ python -m timeit "L = []" "for i in xrange(5000): L += [1]"
1000 loops, best of 3: 1.34 msec per loop

~\$ python -m timeit "L = []" "for i in xrange(25000): L += [1]"
100 loops, best of 3: 6.91 msec per loop

```