[New-bugs-announce] [issue13351] Strange time complexity when creating nested lists

[Jonas LM]

New submission from Jonas LM <quakes0 at gmail.com>:

Consider the following snippets:

def lists(n):
    start_time = time.time()
    lists = [None]*n
    for i in xrange(n):
            lists[i] = [None]*n
            for j in xrange(n):
                    lists[i][j] = []
    print time.time() - start_time

def simple_lists(n):
    start_time = time.time()
    lists = [None]*n
    for i in xrange(n):
            lists[i] = [None]*n
            for j in xrange(n):
                    lists[i][j] = False
    print time.time() - start_time

Both of these snippets seem like they should run in O(n^2), right?

Observe the following test runs:

>>> for i in [4000, 8000, 16000]: simple_lists(i)
2.11170578003
8.67467808723
34.0958559513
>>> for i in [1000, 2000, 4000]: lists(i)
1.13742399216
7.39806008339
78.0808939934

While simple_lists() seem to run roughly in O(n^2), it seems like lists() runs in upwards of O(n^3) or worse! Something funky is going on, and I have no idea what.

----------
components: None
messages: 147126
nosy: quakes
priority: normal
severity: normal
status: open
title: Strange time complexity when creating nested lists
type: performance
versions: Python 2.6

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13351>
_______________________________________