Quiz 1: Complexity of len(str(number))
Consider the following code:
digits = len(str(number))
Question:
What are the time and space complexities of this operation, assuming number has N decimal digits?
Answer to Quiz 1
- Time complexity: O(N)
- Space complexity: O(N)
This is because str(number) must construct a full decimal representation of the integer.
That requires processing every digit and allocating memory proportional to the number of digits.
This behavior is fundamental and unavoidable for an exact result.
Quiz 2: Can you do this with O(1)?
Since converting to a string takes O(N) time and memory, a natural follow-up question is:
Can we count the number of digits of a Python integer in O(1) time without allocating additional memory?
You might think of approaches using logarithms (log10).
So, is an exact O(1) solution possible?
Answer to Quiz 2
No, an exact O(1) solution is not possible in Python.
Why not?
Python integers are arbitrary-precision integers. Internally, they are stored in binary (base 2), not in decimal.
Most importantly:
Python integers do not store their decimal digit count.
They only store binary limbs. When you ask for the number of decimal digits, Python must derive that information from the internal representation.
From an information-theoretic perspective:
- The result depends on N decimal digits
- Determining it exactly requires examining information proportional to N
Therefore, any exact algorithm for counting decimal digits must take O(N) time in the worst case.
What about log10?
Methods based on:
int(math.log10(number)) + 1
do not give an exact result and still require converting the big integer to a float, which is O(N). They also rely on finite-precision floating-point arithmetic.
They can fail at boundary cases—especially for very large integers—so they are not correct general solutions.
Fundamentally, the loss of correctness comes from converting an arbitrary-precision integer into a finite-precision floating-point number. On top of that, differences in OS libraries and CPU implementations can further affect rounding behavior.
Takeaway
len(str(number))is O(N) time and space, and that cost is inherent- There is no exact O(1) digit-counting method for Python integers
- The limitation comes from Python’s internal integer representation