[Tutor] Question about O(N**2)

[Danny Yoo]

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.