Python MIT lectures : log(n) complexity of the example

Question

There is a code from MIT python programing course , lecture 8 .

def(x):
    assert type(x) == int and x >= 0
    answer = 0 
    s = str(x)
    for c in s :
        answer += int(c)
    return answer 

As professor says , complexity of this code is log base 10 of (x). He explains it (as i was able to understand) that, each loop iteration, C can be one of the ten digits (0-9) and this brings base 10 to logarythm.

However i cannot understand , why it is so? Cause complexity actually depends of the length of list S , rather than variations of choice for C.

Can somebody explain ?

Answer 1

The time spent depends on the number of digits in x as a decimal number. The number of digits in a positive decimal number x is floor(log10(x)) + 1 (Wikipedia has a good explanation as to why this is true):

>>> from math import log10
>>> 
>>> x = 12345
>>> int(log10(x)) + 1
5

Hence the time complexity goes as log10, as the professor states. In other words, as x increases, the number of digits we need to process increases as log10(x).