What is the run time of String.toCharArray()?

Question

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.

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
– MrSmith42, Commented Dec 27, 2012 at 23:57
@irrelephant So it's probably O(1)? Since it's not iterating through a loop but copying a memory block? — cinnamon toast
– cinnamon toast, Commented Dec 28, 2012 at 0: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 stackoverflow.com/a/2589962/485971 — irrelephant
– irrelephant, Commented Dec 28, 2012 at 0:14
@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
– Chris Dargis, Commented Dec 28, 2012 at 0:55

NPE · Accepted Answer · 2013-01-05 12:45:56Z

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.

Collectives™ on Stack Overflow

What is the run time of String.toCharArray()?

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related