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
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