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

[Devin Jeanpierre]

On Sat, May 3, 2014 at 9:13 PM, Steven D'Aprano <steve at 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