CODEWITHSUNDEEP
javatime-complexity
zcahfg2
zcahfg2

Reputation: 881

Time complexity of Stringbuilder subSequence method

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?

Upvotes: 0

Views: 470

Answers (2)

Jochen Reinhardt
Jochen Reinhardt

Reputation: 843

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).

Upvotes: 0

tobias_k
tobias_k

Reputation: 82899

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);
}

Upvotes: 1

Related Questions