costadvl costadvl - 1 month ago 22
Python Question

Python log(n) complexity

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

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