On Sat, May 3, 2014 at 9:13 PM, Steven D'Aprano <st...@pearwood.info> wrote: > > 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).
Nit: starting from an empty list, it's worst-case O(N), no "amortized" qualifier necessary. -- Devin _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
