Time complexity of StringBuilder reverse method

Question

I want to find the time complexity of StringBuilder reverse method. Here the source code of the reverse method:

 public AbstractStringBuilder reverse() {
        boolean hasSurrogate = false;
        int n = count - 1;
        for (int j = (n-1) >> 1; j >= 0; --j) {
            char temp = value[j];
            char temp2 = value[n - j];
            if (!hasSurrogate) {
                hasSurrogate = (temp >= Character.MIN_SURROGATE && temp <= Character.MAX_SURROGATE)
                    || (temp2 >= Character.MIN_SURROGATE && temp2 <= Character.MAX_SURROGATE);
            }
            value[j] = temp2;
            value[n - j] = temp;
        }
        if (hasSurrogate) {
            // Reverse back all valid surrogate pairs
            for (int i = 0; i < count - 1; i++) {
                char c2 = value[i];
                if (Character.isLowSurrogate(c2)) {
                    char c1 = value[i + 1];
                    if (Character.isHighSurrogate(c1)) {
                        value[i++] = c1;
                        value[i] = c2;
                    }
                }
            }
        }
        return this;
    }

Here's a link to the doc: documentation Which is the time complexity?

Is there any way to perform more efficiently the reversion of a String?

Answer 1

Reverting a mutable string implies relocating at least half of the characters (if you do it in-place), so that is O(n) complexity. The code you posted has two loops, confirming it's O(n).

On a more thoeretical note, the entire StringBuilder implementation could be devoted to O(1) inversion, such that you only set a flag and then all the methods honor it by interpreting the array contents either front-to-back or back-to-front. I say "theoretical" because there's no point in increasing the complexity of everything, making it slower as well, just to have O(1) string inversion.