4
\$\begingroup\$

I've been reading Cracking the Coding Interview and at the very beginning I got to the strange statement that the next complexity will be \$O(n^2)\$.

public String makeSentence(String[] words){
 String sentence = "";
 for (String w:words){
     sentence+=w;
 }
 return sentence;
}

I can't get it. Why is it \$O(n^2)\$? Here I found another article on this topic.

\$\endgroup\$
  • 6
    \$\begingroup\$ This would be more appropriate for Stack Overflow I would think. \$\endgroup\$ – Jeff Mercado Aug 8 '11 at 20:53
16
\$\begingroup\$

For every call to String.concat(), a new string instance is created. To create that instance, the contents of the previous string needs to be copied to the new one plus the contents of the concatenated string. This is done for every string in the collection. So if you look at in in terms of how many strings are concatenated (and not the characters copied), you're copying the contents of the n strings by the time you reach the nth iteration and all that matters is the worst case (the last iteration). Therefore it has \$O(n^2)\$ performance.

\$\endgroup\$
  • \$\begingroup\$ Doesn't this assume that you know how String is implemented in your particular runtime? At the very least the question should indicate what JRE they are talking about. \$\endgroup\$ – Peter Recore Oct 28 '11 at 23:20
  • \$\begingroup\$ @Peter: If you are interviewing for a Java position and you don't know that Java strings are immutable then you have already failed. \$\endgroup\$ – Ed S. Oct 29 '11 at 0:41
  • \$\begingroup\$ @Ed S.: Yes, the javadoc says they are immutable. However, that alone does not lead inevitably to concatenation in a loop exhibiting n^2 behavior. That is a consequence of String's current internal representation. Alternate representations can give you different algorithmic characteristics. I just want the question to be more precise about its assumptions, even if they are assumptions most people make without realizing it. TLDR: String's contract does not guarantee quadratic behavior in the given example, though its current implementation does \$\endgroup\$ – Peter Recore Oct 29 '11 at 3:58
2
\$\begingroup\$

As Jeff points out a new string is created every time you do += on the string.
And thus correctly explains why the complexity is O(2)

The key point is the java.lang.String is not mutable.

Strings are constant; their values cannot be changed after they are created. String buffers support mutable strings. Because String objects are immutable they can be shared.

So any attempt to modify it generated a completely new string (which to programmers in most other languages is strange).

The solution is to use the java.lang.StringBuffer. This behaves like most other languages string object and allows mutation. The objective is to build a string inside a StringBuffer and when you are finally finished covert this into a string.

A thread-safe, mutable sequence of characters. A string buffer is like a String, but can be modified. At any point in time it contains some particular sequence of characters, but the length and content of the sequence can be changed through certain method calls.

\$\endgroup\$
  • 2
    \$\begingroup\$ StringBuilder should be used over StringBuffer for new code that doesn't need to work under 1.4 JVMs or earlier. "Where possible, it is recommended that this class be used in preference to StringBuffer as it will be faster under most implementations." \$\endgroup\$ – Mike Samuel Aug 9 '11 at 18:58
  • 1
    \$\begingroup\$ Agree with @Mike - StringBuilder should be used here over StringBuffer - The builder itself isn't visible outside the scope of the method, so there isn't any problem regarding threading issues/ \$\endgroup\$ – Clockwork-Muse Aug 9 '11 at 20:51
  • \$\begingroup\$ @Mike: I would be more than happy to vote your answer up. My Java was good many moons ago but it is not currently my main language. \$\endgroup\$ – Martin York Aug 9 '11 at 21:18
  • \$\begingroup\$ @Martin, I can't add anything to your answer besides this minor quibble so have no answer for you to vote on. \$\endgroup\$ – Mike Samuel Aug 9 '11 at 21:20
1
\$\begingroup\$

Immutability is not really the issue here. It is possible to write a mutable string class where this still would be \$O(n^2)\$ or an immutable string class of lower complexity (Sun could have done the latter anyway). The problem here is that at each iteration, the algorithm is rereading the string from the previous iteration in order to produce a new string.

To reduce it by an order of magnitude, you need to shift references. In some cases, the compiler very well might do this anyway, depending upon the sophistication of code optimization. In the case of the class String however, I think it still does it the expensive way, by design.

StringBuffer may be mutable, but I don't see how that is what makes it more efficient in this case. What matters is that at each iteration, it simply appends a reference to the list of characters instead of reads each item for any reason, whether to copy them into a new string instance as String does in this example, or for some other silly reason. But to focus on this as a mutability/immutability issue I think misses the point.

Simple illustration of what I mean. Input a string of letters. At each iteration, you read the previous string to create a new string, and then the current index of the input string to append to the new string. The general relation is the length of the string produced by the previous iteration plus one, which gives you a complexity of \$n^2 - 1\$, or \$O(n^2)\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.