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).
Python's standard list implementation in C uses a strategy of
geometric array resizing whenever the capacity has been exceeded. It
expands the capacity by a multiplicative factor of its current
capacity. Amortized analysis, a subject in computer science, lets us
discover that the cost spread across many operations will be O(n).
References:
http://en.wikipedia.org/wiki/Dynamic_array
---
What can be O(n^2) is the related, but not identical scenario where:
fullPath += ...
where fullPath is an immutable string. But this scenario is different
than the original one.
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
