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?

Question

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?

Answer 1

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.