patternjavaModerate
String manipulation complexity
Viewed 0 times
manipulationstringcomplexity
Problem
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)\$.
I can't get it. Why is it \$O(n^2)\$? Here I found another article on this topic.
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.
Solution
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.Context
StackExchange Code Review Q#3972, answer score: 17
Revisions (0)
No revisions yet.