[FIXED] What is the time complexity of type casting function in python?

Issue

For example, int(x) float(x) str(x) What is time complexity of them?

Solution

There is no definite answer to this because it depends not just what type you're converting to, but also what type you're converting from.

Let's consider just numbers and strings. To avoid writing "log" everywhere, we'll measure the size of an int by saying n is how many bits or digits it takes to represent it. (Asymptotically it doesn't matter if you count bits or digits.) For strings, obviously we should let n be the length of the string. There is no meaningful way to measure the "input size" of a float object, since floating-point numbers all take the same amount of space.

• Converting an int, float or str to its own type ought to take Θ(1) time because they are immutable objects, so it's not even necessary to make a copy.
• Converting an int to a float ought to take Θ(1) time because you only need to read at most a fixed constant number of bits from the int object to find the mantissa, and the bit length to find the exponent.
• Converting an int to a str ought to take Θ(n²) time, because you have to do Θ(n) division and remainder operations to find n digits, and each arithmetic operation takes Θ(n) time because of the size of the integers involved.
• Converting a str to an int ought to take Θ(n²) time because you need to do Θ(n) multiplications and additions on integers of size Θ(n).
• Converting a str to a float ought to take Θ(n) time. The algorithm only needs to read a fixed number of characters from the string to do the conversion, and floating-point arithmetic operations (or operations on bounded int values to avoid intermediate rounding errors) for each character take Θ(1) time; but the algorithm needs to look at the rest of the characters anyway in order to raise a ValueError if the format is wrong.
• Converting a float to any type takes Θ(1) time because there are only finitely many distinct float values.

I've said "ought to" because I haven't checked the actual source code; this is based on what the conversion algorithms need to do, and the assumption that the algorithms actually used aren't asymptotically worse than they need to be.

There could be special cases to optimise the str-to-int conversion when the base is a power of 2, like int('11001010', 2) or int('AC5F', 16), since this can be done without arithmetic. If those cases are optimised then they should take Θ(n) time instead of Θ(n²). Likewise, converting an int to a str in a base which is a power of 2 (e.g. using the bin or hex functions) should take Θ(n) time.

Answered By - kaya3