Convert string to number & vice versa complexity

Question

What would be the complexity of converting a string to its equivalent number or vice versa? Does it change depending on programming language?

On the face of it, one needs to traverse the entire string to convert it to a number, so it is O(n), or is some typecasting used?

This doubt came about when I was writing a routine to check if a given number is a palindrome or not. One approach would be to keep dividing the number by the base (here 10), accumulate digits, and put them together at the end. Example: 309/10=rem(9), 30/10=rem(0), 3/10=rem(3). we get 903.

Another approach I took was to convert this number into a string, and since strings have loads of member functions to split, reverse etc., the code was a lot shorter and cleaner, but is this the best way to do this?

Answer 1

Numeric strings are numbers formatted in positional notation - so the value of each digit multiplied by a power of the base needs to be taken into account in order to convert the number into a binary format.

So yeah, it's an O(N) operation because the running time increases linearly as more digits are added. However, in practice N may be limited by whatever numeric data-types the language supports (e.g. int32_t, int64_t). But if arbitrary precision number types are used (which some languages, like Python, use by default) then there is no limit to the number of digits (other than available memory obviously).

Answer 2

To convert to a number you always have to read all digits. So it's at least O(n).

Now doing something like (pseudocode)

a = 0
foreach digit in string
do
   a = 10 * a + digit
end

Is O(n). So the complexity is O(n)