What is the runtime of toCharArray() and toString() in Java?
algorithm, arrays, data-structures, java
Solution
Conversion of `BigInteger` to string is `O(N^2)`, where `N` is the number of digits in the result, when the base of the internal representation does not divide the target base; when the target base is divisible by the storage base, conversion takes `O(N)`.
Consider conversion to base 10 when the internal representation is base-256. A division by ten has to happen `N` times; each time, all elements of the `BigInteger` representation get modified. The number of elements in the representation is proportional to the number of digits in the printout, so the overall conversion takes `O(N^2)`.
On the other hand, converting to hex of a big int in base-256 internal representation takes `O(N)`, because division is not necessary in this case. Each subelement can be converted in isolation from the remaining ones, and the number of sub-elements is proportional to the number of digits in the printout.
As far as `String.toCharArray()` goes, it's `O(N)`, where `N` is the number of characters in the string, because each character must be copied into the output.
Problem
What is the performance of these? ``` BigInteger -> toString() // what is the runtime? String -> toCharArray() // what is the runtime? ``` Thanks.