Python log(n) complexity

Question

I cannot understand why this is a log(n) complexity code.

def intToStr(i):

    digits = '0123456789'

    if i == 0:

        return '0'

    result = ''

    while i > 0:

        print(1)

        result = digits[i%10] + result

        i = i//10

    return result

Answer 1

Expanding on Abhihit's answer, you need to calculate the amount of steps:

while i > 0:
    i = i // 10

will take. Well suppose you start at i = n. The amount of steps is the amount of times a product of 10 will 'fit' in i (since you divide out 10 each time). This is the digit mentioned above. So the relation between the amount of steps and n is:

n=10^steps

There is a 'leftover' or modulues, but in integer division it doesn't matter (it may add 1 to the steps). So solving for steps:

steps=log n

Python log(n) complexity

Sign up