costadvl - 6 months ago 71

Python 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

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