6

What's the run time of String.toCharArray() in java? The source code is 

 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;
}

Does System.arrayCopy? have run time of O(n)? The source code doesn't really say much about how it's implemented. Does it go through every element and copies it? Thanks.

cinnamon toast
  • 177
  • 1
  • 8
  • I am very sure runtime is **O(n)** it can't be better (the characters have to be copied). Question is what is the factor. – MrSmith42 Dec 27 '12 at 23:57
  • 4
    See this answer: http://stackoverflow.com/a/11208577/485971 – irrelephant Dec 27 '12 at 23:58
  • @irrelephant So it's probably **O(1)**? Since it's not iterating through a loop but copying a memory block? – cinnamon toast Dec 28 '12 at 00:05
  • Not really - I think it's still O(N) but with a low constant factor, as @MrSmith42 says. Sometimes it may have a higher constant factor - see http://stackoverflow.com/a/2589962/485971 – irrelephant Dec 28 '12 at 00:14
  • Offtopic question, maybe but -- why do you care? – fge Dec 28 '12 at 00:30
  • @fge for an algorithm that returns some info about the input strings or compare multiple strings, I can't achieve it in less than O(n) time if using `String.toCharArray()`. But a lot of times, it's easier to work w/ the string if it's converted to an array. – cinnamon toast Dec 28 '12 at 00:49
  • 2
    @cinnamontoast: Even if the method is copying *blocks* of memory, it still can't be `O(1)`. I would say, the run-time is still `O(N)`, where `N` is the number of blocks. Granted this is a faster approach, you still have to copy all of the blocks. – Chris Dargis Dec 28 '12 at 00:55

1 Answers1

5

System.arraycopy() is typically an intrinsic and is very fast. That said, it still has to look at (and copy) every element of the array, so its asymptotic complexity is linear in the length of the array, i.e. O(n).

Thus the complexity of toCharArray() is O(n), where n is the length of the string.

NPE
  • 486,780
  • 108
  • 951
  • 1,012