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

You could take a look at the source code...or read the javadoc. — Sotirios Delimanolis, Mar 26 '14 at 21:49
http://stackoverflow.com/questions/7165594/time-complexity-of-system-arraycopy — jmj, Mar 26 '14 at 22:01

Piotrek Hryciuk · Accepted Answer · 2015-07-03T11:23:53.410

7

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

edited Jul 03 '15 at 11:23

answered Mar 26 '14 at 21:51

Piotrek Hryciuk

785
10
23

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. – Charlie Mar 26 '14 at 21:59
1

That means a low constant factor, not a change in the actual asymptotics. – Louis Wasserman Mar 26 '14 at 22:09

score 1 · Answer 2 · answered Mar 26 '14 at 21:49

1

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

answered Mar 26 '14 at 21:49

Louis Wasserman

191,574
25
345
413

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

2 Answers2