CODEWITHSUNDEEP
javastring
C graphics
C graphics

Reputation: 7458

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

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)?

Upvotes: 6

Views: 11410

Answers (3)

Abhijith Ravindran
Abhijith Ravindran

Reputation: 521

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.

Upvotes: 0

Piotrek Hryciuk
Piotrek Hryciuk

Reputation: 805

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

Upvotes: 9

Louis Wasserman
Louis Wasserman

Reputation: 198391

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

Upvotes: 3

Related Questions