CODEWITHSUNDEEP
javastringbuilder
sjx
sjx

Reputation: 39

Time complexity for creating a string with stringbuilder object in Java

If I have a StringBuilder object sb, what's the time complexity when I try to create a new string with the code new String(sb)? See below for an example. Should it be O(n) since it creates a string with a deep copy of the original sb? Thanks.

StringBuilder sb = new StringBuilder();
sb.append('a');
sb.append('b');
String c = new String(sb);

Upvotes: 2

Views: 557

Answers (1)

O. Jones
O. Jones

Reputation: 108641

Yup. O(n). That's why it's in the library. The same is true for C#.

Strings, in both languages, are immutable. So building reports and other text documents with successive string concatenation is O(n squared).

The developers for the StringBuilder class in both languages have invested a lot of brain power and testing time in making it really fast. The same is true for the other core collection classes of course.

If you can refactor some successive concatenation code with StringBuilder code, you will become revered as a performance optimization wizard.

Beware StringBuffer. It has similar semantics but it happens to be thread safe, which slows it down a lot.

Upvotes: 3

Related Questions