Since Java 7, String substring method has changed its big O from O(1) to O(n).
What is the time complexity of StringBuilder subSequence method?
Add a comment
|
2 Answers
In java-11-openjdk, AbstractStringBuilder.subSequence calls substring...
public CharSequence subSequence(int start, int end) {
return substring(start, end);
}
... which is almost identical to the method of the same name of String ...
public String substring(int start, int end) {
checkRangeSIOOBE(start, end, count);
if (isLatin1()) {
return StringLatin1.newString(value, start, end - start);
}
return StringUTF16.newString(value, start, end - start);
}
... calling newString which will (in both cases) copy the backing array, so it's O(n), too.
public static String newString(byte[] val, int index, int len) {
return new String(Arrays.copyOfRange(val, index, index + len),
LATIN1);
}
Comments
I don't know where you have found this info. O(1) to O(n) for substring?
The complexity for StringBuilder.subSequence(int start, int end) will roughly be the same as for String.substring(int start, int end).
StringBuilder.subSequence(int, int) actually calls AbstractStringBuilder.substring(int, int) which calls public String(char value[], int offset, int count) to create the result.
String.substring(int start, int end) uses the same constructor.
So all the methods have the same implementation.
The work is done in the string construtor. It uses System.arrayCopy to copy the chars from one buffer to the other. So it is not doing an assignment for each single character (which would make it O(n), where n is not the length of the input, but the length of the substring), but using a high-performance system function to copy a block of memory, which is a lot better than O(n).
2 Comments
zcahfg2
stackoverflow.com/questions/4679746/… Prior to Java 7, it used same char[] so the cost is the time taken to perform validation and construct a single new string O(1).
tobias_k
But even if
System.arrayCopy is very fast, it is still O(n), right?