Space complexity of a recursive algorithm

Question

I have a recursive algorithm to find a palindrome in Java. It should return true if the given string is palindrome. False otherwise. This method uses substring method, which is little bit trickier to find the complexity.

Here's my algorithm:

static boolean isPalindrome (String str) {
    if (str.length() > 1) {
        if (str.charAt(0) == (str.charAt(str.length() - 1))) {
    if (str.length() == 2) return true;
            return isPalindrome(str.substring(1, str.length() - 1));
        }
        return false;
    }
    else {
        return true;
    }
}

What is the space complexity of this algorithm ?

I mean, when I call the method substring(), does it create a new string all the time ? What actually substring method do in Java ?

Answer 1

In older versions of Java (mainly in Java 6 and before)*, substring returned a new instance that shared the internal char array of the longer string (that is nicely illustrated here). Then substring had time and a space complexity of O(1).

Newer versions use a different representation of String, which does not rely on a shared array. Instead, substring allocates a new array of just the required size, and copies the contents from the longer string. Then substring has a time and a space complexity of O(n).

_{*Actually the change was introduced in update 6 of Java 7.}