String Concatenation O(n^2) (was: Re: Explaining Implementing a Binary Search Tree.)

[Bart Kastermans]

On Jun 17, 1:01 am, "Gabriel Genellina" <gagsl-... at yahoo.com.ar>
wrote:
> En Mon, 16 Jun 2008 07:34:06 -0300, Bart Kastermans <bkast... at gmail.com> escribió:
>
> > Summary: can't verify big O claim, how to properly time this?
>
> > This is interesting.  I had never attempted to verify a big O
> > statement
> > before, and decided that it would be worth trying.  So I wrote some
> > code to
> > collect data, and I can't find that it goes quadratic.
>
> In your test code, you're concatenating only two strings, that's a *single* operation, and takes time proportional to the total length.
> The quadratic behavior appears when you do *several* concatenations in a row (like in your original code, where += was used several times to build a result).
> If you want to verify it, try joining N strings of size M (for varying values of N and M), and plot total time vs. N (for a given M value), and total time vs. M (for a given N value) and finally total time vs. (N*M), see what happens and post your findings again.
>
> --
> Gabriel Genellina

I did the work and found that for trees it does not go quadratic at
all, from the computations you suggest it is easy to get quadratic
behavior though.  Also this does not depend in any way I can see on
the implementation by Python.  Actual time might certainly improve by
doing it differently (changing the constants), but the big O results
won't.

For pictures and math I have put it up on my blog again see:
http://kasterma.wordpress.com/2008/06/21/complexity-of-string-concatenation-ii/

Thanks to everyone who commented so far on this subject.  I had some
good fun with it so far.

Best,
Bart