HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaModerate

String manipulation complexity

Submitted by: @import:stackexchange-codereview··
0
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)\$.

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.