For example,
int(x)
float(x)
str(x)
What is time complexity of them?
Asked
Active
Viewed 6,951 times
13
-
It depends on the argument type. `int(x)` is O(1) if `x` is already an `int`, but it's O(n) for a `str` of length `n`. – chepner Mar 21 '20 at 14:01
-
4btw, there is no casting in python. What you are using are conversion functions. – quamrana Mar 21 '20 at 14:02
-
3`str` can be arbitrarily complex because it calls the object's `__str__` method which is free to do whatever it likes. – tdelaney Mar 21 '20 at 14:11
2 Answers
10
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,floatorstrto 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
intto afloatought to take Θ(1) time because you only need to read at most a fixed constant number of bits from theintobject to find the mantissa, and the bit length to find the exponent. - Converting an
intto astrought to take Θ(n2) 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
strto anintought to take Θ(n2) time because you need to do Θ(n) multiplications and additions on integers of size Θ(n). - Converting a
strto afloatought 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 boundedintvalues 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 aValueErrorif the format is wrong. - Converting a
floatto any type takes Θ(1) time because there are only finitely many distinctfloatvalues.
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 Θ(n2). 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.
kaya3
- 47,440
- 4
- 68
- 97
-
-
I think str->int takes O(n), you can easily do it over looping the string, then sum `sum_ += i * 10**end_index` end_index is the last element's index in str – Rustam-Z Jan 31 '22 at 03:40
-
@Rustam-Z That would also be an O(n^2) algorithm. `10**end_index` takes O(n) time because it creates an `int` object with O(n) bits, and the additions would be O(n) each for the same reason. – kaya3 Jan 31 '22 at 06:14
-
the complexity of math.pow(x, y) is O(1) -> https://stackoverflow.com/questions/48839772/why-is-time-complexity-o1-for-powx-y-while-it-is-on-for-xy – Rustam-Z Jan 31 '22 at 08:21
-
1
-2
Float(x) is more complex among these, as it has a very long range. At the same time it depends on how much of the value you are using.
-
1Regarding range: `float` is the smallest type, as it has a finite number of values it can store. The number of possible `int` and `str` values is limited only by your machine's memory. – chepner Mar 21 '20 at 14:28