Strings joining and complexity?

Question

When I need to join two strings I use String.Format (or StringBuilder if it happens in several places in the code).

I see that some good programmers doesn't give attention to strings joining complexity and just use the '+' operator.

I know that using the '+' operator make the application to use more memory, but what about complexity?

Answer 1

This is an excellent article about the different string join methods by our own Jeff Atwood on Coding Horror:

_{(source: codinghorror.com)}

The Sad Tragedy of Micro-Optimization Theater

Here is the gist of the post.

[several string join methods shown]

Take your itchy little trigger finger off that compile key and think about this for a minute. Which one of these methods will be faster?

Got an answer? Great!

And.. drumroll please.. the correct answer:

It. Just. Doesn't. Matter!

Answer 2

This answer assumes you are talking about the runtime complexity.

Using + creates a new string object, which means the contents of both the old string objects must be copied into the new one. With a large amount of concatenation, such as in a tight loop, this can turn into an O(n^2) operation.

As an informal proof, say you had the following code:

string foo = "a";
for(int i = 0; i < 1000; i++)
{
    foo += "a";
}

The first iteration of the loop, first the contents of foo ("a") are copied into a new string object, then the contents of the literal "a". That's two copies. The second iteration has three copies; two from the new foo, and one from the literal "a". The 1000th iteration will have 1001 copy operations. The total number of copies is 2 + 3 + ... + 1001. In general, if in a loop you are only concatenating one character each iteration (and you start at one character long), if the number of iterations is n, there will be 2 + 3 + ... + n + 1 copies. That's the same as 1 + 2 + 3 + ... + n = n(n+1)/2 = (n^2 + n)/2, which is O(n^2).