Complexity Analysis
def count_digits(n):
count = 0
while n > 0:
count += 1
n //= 10
return countWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(log n)
Space
O(1)
How to derive it
Each iteration divides n by 10. A number n has floor(log₁₀(n)) + 1 digits, so the loop runs O(log n) times. The base of the logarithm doesn't matter in Big-O (log₁₀ and log₂ differ by a constant factor).