CODEWITHSUNDEEP
javastringsubstringtime-complexitystringbuilder
Yuanwei Chen
Yuanwei Chen

Reputation: 51

What is the time complexity of Java StringBuilder.substring() method? If it is linear, is there a constant time complexity method to get a substring?

In my opinion it should be constant(O(1)) time complexity. However I was told that a new String object has to be instantiated when invoking stringBuilder.substring() method. (It is not static method). If this is true, how can I get a substring within a constant time complexity?

Upvotes: 4

Views: 5975

Answers (3)

Nagappan
Nagappan

Reputation: 356

StringBuilder's substring actually copies the characters from start index to end index, so it tries to array copy of characters of substring length(i.e end index-startindex). This will be the time complexity of this operation O(substringlength) as the loop runs from start index to end index which cannot be avoided. With this the substring char[], string object will be instantiated.

Upvotes: 0

Marko Topolnik
Marko Topolnik

Reputation: 200168

You cannot possibly create a String from a StringBuilder in constant time and have its immutability maintained. Additionally, as of Java 7 Update 25, even String#substring() is linear time because structural sharing actually caused more trouble than it avoided: substring of a huge string retained a reference to the huge char array.

Upvotes: 3

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726589

In my opinion it should be constant(O(1)) time complexity.

This is not possible. Since Java strings are immutable, while StringBuilders are mutable, all operations that produce a String must make a copy.

If this is true, how can I get a substring within a constant time complexity?

You cannot. Without a copy, changing characters inside a substring would mutate the String, which is not allowed.

Upvotes: 2

Related Questions