Big O Notation for space complexity of converting a string to char array

user_5868705 0
Viewed 1005

Given a string String str= "absdf"; of N length and if we convert the same string to char Array using - char [] arr=str.toCharArray();.

Is it consider to be an extra space of O(N) or it will be O(1)?

big-o java
4 Answers

It is O(N) as suggested by @andy, the implementation of String.toCharArray() is something like:

public char[] toCharArray() {
  char result[] = new char[value.length];
  // copy the contents
  return result;
}
user_13275850

Time Complexity will be O(N). Similar to creating a new Array equal to the length of the String and copying the String to the Character Array. Creating an array takes O(N) time and copying takes O(N). So total worst case complexity will be O(N).

user_103675950

Its O(N)

public char[] toCharArray() {
    // Cannot use Arrays.copyOf because of class initialization order issues
    char result[] = new char[value.length];
    System.arraycopy(value, 0, result, 0, value.length);
    return result;
}

This code is taken from openjdk implementation. We are trying to iterate each element of string and copy it into the each cell of array. Number of iteration will be length of string.

user_130960090

As per Official java doc toCharArray() creates a newly allocated character array whose length is the length of a given string and whose contents are initialized to contain the character sequence represented by the given string. As it's copying each character from string to char array it takes linear time, so Time complexity is O(n), and space complexity is also O(n).

user_197000180
Related