What is the time complexity of String.toCharArray(), O(n) or O(1)

Question

Suppose you want to convert a String of length n to a character array of length n.

char [] chArray = someString.toCharArray();

What is the computation complexity?O(n) or O(1) ( n: length of someString)

I am under the impression that all it does is to allocate memory of size n*sizeof(char) and make a copy of that string to that location. So copying n cells of memory takes O(n) time. Is it ?

or it could be O(1), ( simple pointer relocation or as mentioned here)?

• Sotirios Delimanolis: You could take a look at the source code...or read the javadoc.
• Jigar Joshi: System.arrayCopy() works on O(N)
• C graphics: @JigarJoshi why not posted as an answer?
• Jigar Joshi: stackoverflow.com/questions/7165594/…

Answer 1

The answer is linear time.

Think of it as copying single char and putting it into an array. It depends on number of elements so it's O(n).

• Charlie: Although the copy for n=0 through n=512 might be the same duration and might go up in increments of some larger constant value.
• Louis Wasserman: That means a low constant factor, not a change in the actual asymptotics.

Answer 2

It's linear time; it does the copy, and copies take linear time. (The constant factor might be quite low, but it's still linear overall.)

Answer 3

The time complexity of the String.toCharArray() method in Java is O(n), where n is the length of the string. Here's a detailed breakdown:

Underlying Implementation:

A Java String internally stores characters in a char[] array. However, this array is private and immutable.

When you call toCharArray(), the method creates a new array and copies the characters from the String's internal array to this new array. This ensures the String's immutability is preserved.

Java Source Code: The actual implementation (from OpenJDK) is:

public char[] toCharArray() {
 char[] result = new char[value.length];
 System.arraycopy(value, 0, result, 0, value.length);
 return result;
}

new char[value.length] allocates a new array of size n.

System.arraycopy(...) copies all n characters from the String's internal array to the new array. This is an O(n) operation.

If Java returned the internal array directly (without copying), it would expose mutable access to the String's data, violating its immutability. For example:

String s = "hello";
char[] arr = s.toCharArray();
arr[0] = 'x'; // This should NOT modify the original string.

A copy is required to prevent this.

Example For a string "hello" (length 5):

A new char[5] is allocated.

All 5 characters ('h', 'e', 'l', 'l', 'o') are copied into the new array.

The copy operation takes O(n) time (linear with respect to the string's length).

So in Summary: Time Complexity: O(n) (linear time).

Reason: The method creates a new array and copies all n characters from the String's internal storage to this array. There’s no way to bypass this copying step in Java.