Reverse String in Java
Linear in space

Both are linear in space.  

The first one is linear because the StringBuilder makes a copy of the string.  

The second one is linear because toCharArray makes a copy of the string.  We know it can't use the backing array of the string, because the string is immutable.  Clearly you can modify the character array.  We can ignore the swap variable (c), as it is either constant space or 

We can consider a Java compiler (even if none currently work this way) that would release the backing array to the toCharArray, but we can't guarantee that.  Because the calling code may want to use the string after calling this method.  So the assumption in the method is that we are creating a new array.  

If the input is a string and the output is a different string (and we can't change the original string, so it has to be different), then linear time is the best we could possibly do.  So even without the intermediate variable, these would still be linear in space.  Both create new strings.  

Linear in time

Both are linear in time.  

The first one does \$n\$ iterations with one append operation per iteration.  The append operations should be constant time.  There may be occasional copy operations that can be amortized to be constant time per append operation or linear time overall.  That's \$\mathcal{O}(n)\$.  

The second one does \$\frac{n}{2}\$ iterations with two array assignments per iteration.  That's also linear, \$\mathcal{O}(n)\$.  Because \$\frac{n}{2}\$ grows linearly with \$n\$ and two is a constant.  

Constant space

To have a method be constant in space, it needs to return the same memory that brings the input.  E.g. 

public void reverse(char[] chars) {
    for (int i = 0, j = chars.length - 1; i &lt; j; i++, j--) {
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
}


This is constant in space and linear in time.  But it neither takes nor returns a string.  

Constant space and time

There's a sort of backwards way of reversing a string in constant time and space.  

class ReversedString {

    private String string;

    public ReversedString(String string) {
        this.string = string;
    }

    public char charAt(int index) {
        return string.charAt(string.length() - 1 - index);
    }

}


But we wouldn't be able to just use this as a string without creating a new string.  The only operation that works (so far) is charAt.  We might be able to make other operations work, but not all of them.  In particular, a toString would be linear in time and space, just like the original methods.  Because it would have to make a new string of the same length.