O(n)??? Can someone tell me the big O of .reverse

Question

say I use the following methods to search for a palindrome. I know the first one is O(n) because it goes through entire string. Does the .reverse() in the StringBuffer also do O(n)? Im not worried about finding a better way to problem Im trying to understand if the reverse method physically reverses the string or is it much more efficient than that?? Thanks

public static boolean isAPalindrome(String s1){

    String tmp = "";    
    int length = s1.length();
    for(int i = 0; i < s1.length(); i++){           
        tmp += s1.charAt(s1.length()-i-1);
    }       
    if (s1.equals(tmp)) return true;
    return false;           

}

public static boolean isAPalindrome(String s1){

    StringBuffer a = new StringBuffer(s1);
    return s1.equals(a.reverse().toString());

}

http://stackoverflow.com/questions/2439141/what-is-the-most-efficient-algorithm-for-reversing-a-string-in-java — novice, Jan 20 '16 at 19:01

Idos · Answer 1 · 2016-01-21T09:39:47.173

0

Reversing a string can't be faster than O(n) (under normal representation of a String).
You have to "operate" on every character of the string, so it can't theoretically be faster than that.

StringBuffer extends AbstractStringBuilder which implements reverse. You may look at the souce code yourself here.

Note: this is not saying that StringBuilder/Buffers reverse will run as fast as an O(n) reverse method that you will write. It will probably run much faster. But asymptotically it will still be O(n).

edited Jan 21 '16 at 09:39

answered Jan 20 '16 at 19:02

Idos

15,053
14
60
75

1

This, if you reverse a problem that has to check either solution or something its just the same and no better. Just a different solution with no inherit advantage. – jgr208 Jan 20 '16 at 19:04
This is simply not true. You can very well have a datastructure for strings with a constant-time reverse operation. – Emil Vikström Jan 21 '16 at 09:17
@EmilVikström care to elaborate? The OP obviously didn't ask about any obscure representations of Strings. Any "normal" one would require O(n) at the very least. – Idos Jan 21 '16 at 09:19
You said that it *can't* be faster. Dirk's answer provides a possible way to make it faster (a double-linked list with a directionality flag). That doesn't matter for OP since they still have the equality check that runs in O(n) but that was not really the question. Yhere is no language tag so I assume the question is about algorithms and datastructures, not about specific implementations. – Emil Vikström Jan 21 '16 at 09:34
I just outright disagree. I could *ofcourse* write a language where *any* operation of your choosing will be o(1), but it would be kinda useless. A string list by it's normal representation wouldn't be able to be reversed under O(n) for obvious reasons (and I stated some). And it is also obvious that the question is about Java since he posted Java code. – Idos Jan 21 '16 at 09:39
In any case I edited my answer slightly to adhere to the "normal" standard – Idos Jan 21 '16 at 09:39

score 0 · Answer 2 · answered Jan 20 '16 at 19:21

You could implement a reverse that is effectively o(1), but not with the typical string classes: You could do it by implementing a string class with a direction member, that can take the values "forward" or "backward". But that would only make sense if the reverting dominates your performance over all other computations.

O(n)??? Can someone tell me the big O of .reverse

2 Answers2