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

[Gabriel Genellina]

En Mon, 16 Jun 2008 07:34:06 -0300, Bart Kastermans <bkasterm 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