The complexity of the algorithm to add to the line in the loop

Consider this question in general for different languages.

The first case. The strings are changeable , the string is a pointer to a certain array (or other data structure) of characters (+ perhaps a wrapper with functions). Examples of languages ​​are С (char *) and С ++ (string).

In this case, the code from the question essentially degenerates into the usual addition of an element to the array. And if this is not a low-quality lab, a handwritten implementation, then the complexity of adding (depreciated) will be no more than the length of what is being added.

Then the complexity of 1 iteration is obviously O (1) and the total is O (len).

The advantages of this approach are the speed of work (addition, the ability to replace characters, the rapid creation of substrings). Cons - you need to be very careful what and how changes in the line, especially in multi-threaded implementations.

And 2 case - the lines are unchangeable . Those. The string object is created once and cannot directly or indirectly change its state. This is typical for Java.

In this case, every time a temporary object is created, the entire old line is copied to + what needs to be added. Those. roughly speaking (pseudocode)

 @s - string r[0] = '' for i =1: i <= s.length(); i++ r[i] = String.gen(r[i-1] , s[i-1]); 

And we create Len lines, length from 0 to Len inclusive, it is easy to see that their total length will be Len * (Len + 1) / 2 ~ O (Len ^ 2).

By the way, in the absence of a normal garbage collector (but usually it is in such languages), you can easily sift from memory.

Pros and cons can say the opposite, it is easier to work but slower.

But in every such language there is a mechanism that allows you to create this without losing performance. This may be a string constructor from the collection or special utility classes (StringBuiled and the like). Using them allows you to significantly speed up the process and achieve in this example the asymptotics O (len).

A smart compiler, if it can prove the equivalence of a code (and in such a simple situation it is not difficult) can replace the direct string concatenation with a utilitarian one, ensuring a speed gain. This is exactly what happened in Python in the example http://ideone.com/wqfd8C .

However, relying on it is dangerous. Quotes from the comments.

Try running Jython for example. Here is a detailed description from the creator of the language. CPython (after 2.5) can sometimes optimize (as a special case) code like r + =. Since it is difficult for newcomers to explain that you should always use '.join instead of s + =. Here is a good answer from Alex Martelli to a related question.

(The link to the question is https://stackoverflow.com/a/1350289/4279 )

To understand the fragility of optimization, compare: python -mtimeit -s' s = "a" * 1,000,000 '$' r = "" \ nfor c in s: \ nr + = c 'and python -mtimeit -s' s = "a "* 1,000,000 '$' r =" "\ nfor c in s: \ nr + = c \ nt = r '

In this case, the compiler lacks “quick-wittedness” and it implements what is written in the “forehead”, which is much slower. Therefore, I repeat, you need to use special language constructs and simplify the life of the compiler.