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: documentationWhich is the time complexity?

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

2

1 Answer

It is impossible to revert a String in less than O(n) and the algorithm you have posted clearly is O(n) since it contains two successive O(n) loops.

3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy