Search code examples
javaarraysstringbig-ospace-complexity

Does toCharArray() consumes space in Big O


In calculating the space complexity of algorithms, we're told the easiest way to find out about additional space is the creation of a data structure like Set, Map, Stack etc.

Take the below code as example that reveres a string (In Java)

private String reverse(String string){

    if (string == null || string.length() == 0) return string;

    char[] strArray = string.toCharArray(); // Does this consume space?

    int first = 0, last = strArray.length - 1;

    while (first < last){
        char temp = strArray[first];
        strArray[first++] = strArray[last];
        strArray[last--] = temp;
    }


    return String.valueOf(strArray);
}

Does converting the str to a character array consume space


Solution

  • According to String's javadoc, toCharArray creates "a newly allocated character array whose length is the length of this string and whose contents are initialized to contain the character sequence represented by this string". Therefore, calling toCharArray has an O(n) space complexity.