Gfrktyl

I've been revamping on my coding puzzles practices. What is the complexity (both time and space) for this method:

public static String reverse(String word) {



    if (word == null || "".equals(word) || word.length() == 1) {

        throw new IllegalArgumentException("Invalid Entry");

    }



    StringBuilder result = new StringBuilder();



    for (int i=word.length() - 1; i >= 0; i--) {

        result.append(word.charAt(i));

    }



    return result.toString();

 }

Is this a more optimized solution (what is the time and space complexity of this one as well):

public static String reverse ( String s ) {

    int length = s.length(), last = length - 1;

    char chars = s.toCharArray();

    for ( int i = 0; i < length/2; i++ ) {

        char c = chars[i];

        chars[i] = chars[last - i];

        chars[last - i] = c;

    }

    return new String(chars);

}

I know that there might be duplicate questions similar to this but am not asking for a solution. I'm only seeking how to figure out the two different types of complexities.

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