I cannot understand why this is a log(n) complexity code.
digits = '0123456789'
if i == 0:
result = ''
while i > 0:
result = digits[i%10] + result
i = i//10
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:
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: