On Sat, May 03, 2014 at 03:59:40PM -0700, Danny Yoo wrote: > Following up on this. Let's make sure that we're talking about the same > thing. > > > The assertion is that the following: > > fullPath += [...] > > where fullPath is a list of strings, exhibits O(n^2) time. I don't > think this is true. Semantically, the statement above should be > equivalent to: > > fullPath.append(...) > > and so I agree with David: this is not O(n^2), but rather O(n).
Danny is correct. For built-in lists, += augmented assignment is implemented using the extend method, not the + operator. Consequently, repeatedly calling += modifies the list in place, growing it as needed, which is amortized O(N) rather than O(N**2). Had += been implemented as + instead, as I initially mis-remembered, the behaviour would have been O(N**2). The process would have gone: fullPath = [] fullPath = [] + [a] # add a new path component fullPath = [a] + [b] fullPath = [a, b] + [c] fullPath = [a, b, c] + [d] fullPath = [a, b, c, d] + [e] ... Each individual + is an O(N+M) operation (if there are ten items in the first list, and five items in the second list, adding them needs to copy fifteen items). With M a constant 1, we can take each addition as O(N). And there are N additions, so we get O(N*N) or O(N**2). We can test this by seeing how long it takes to perform a bunch of additions. For timing, I'm going to use the recipe shown here: http://code.activestate.com/recipes/577896-benchmark-code-with-the-with-statement/ First, using augmented assignment for lists: py> size = 1000000 py> with Timer(): ... data = [] ... for i in range(size): ... data += [i] ... time taken: 0.548546 seconds py> with Timer(): ... data = [] ... for i in range(3*size): ... data += [i] ... time taken: 1.672449 seconds By increasing the amount of data by a factor of three, the time taken also increases by about a factor of three. That is O(N). Now let's try list addition. It's so much slower than += that I had to reduce the size by a lot just to have it complete in any reasonable amount of time: py> size = 10000 py> with Timer(): ... data = [] ... for i in range(size): ... data = data + [i] ... time taken: 0.331893 seconds py> with Timer(): ... data = [] ... for i in range(3*size): ... data = data + [i] ... time taken: 3.203508 seconds Here, increasing N by a factor of 3 takes about 10 times longer, which is consistent with O(N**2). -- Steven _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
