# How can the length of a string be $O(\log n)$?

I have just started learning about time complexities and am currently reading Logarithmic Complexity. Here's an example of a piece of code which is $$O(\log n)$$:

def intToStr(i):
'''Assumes i is a nonnegative int Returns the string representation of i'''

digits = '0123456789'
if i == 0:
return '0'
result = ''
while i > 0:
result = digits[i % 10] + result
i = i // 10
return result


So this just gives is the str of an integer. intToStr(1243) returns '1243'. I completely understand that the above function is of logarithmic complexity.

In continuation,

def addDigits(n):

'''Assumes n is a nonnegative int
Returns the sum of the digits in n'''
stringRep = intToStr(n)
val = 0
for c in stringRep:
val += int(c)
return val


My book says that: (emphasis added)

The complexity of converting $$n$$ to a string is $$O(\log n)$$, and intToStr returns a string of length $$O(\log n)$$. The for loop will be executed $$O(\operatorname{len}(\mathit{stringRep}))$$ times, i.e., $$O(\log n)$$ times. Putting it all together, and assuming that a character representing a digit can be converted to an integer in constant time, the program will run in time proportional to $$O(\log n) + O(\log n)$$, which makes it $$O(\log n)$$.

Can someone please explain how intToStr returns a string of length $$O(\log n)$$? Doesn't it just return a string of length $$n$$, where $$n$$ is the length of the integer that we pass?

## 2 Answers

The length of the binary representation of a natural number $$n$$ is roughly $$\log_2 n$$. As an example, the number represented by the binary string $$10^{n-1}$$ of length $$n$$ is $$2^n$$.

Your sources are misleading. Usually $$n$$ is reserved for the input length or a related quantity, not the input value. If the input to a function is an integer $$m$$, then the input length is only $$\sim \log_2 |m|$$. In particular, intToStr actually runs in linear time in the input length, rather than logarithmic time.

• Hi. I just edited my post to add the complete paragraph, do you still think that it is incorrect? – R Doe. Jun 12 '19 at 13:00
• It is correct, just highly misleading. For a similar example, see cs.stackexchange.com/questions/88398/…. – Yuval Filmus Jun 12 '19 at 13:02
• Can we say that addDigits() is of linear complexity but as it calls intToStr() ( which is of log complexity ), the whole program is of logarithmic complexity? – R Doe. Jun 12 '19 at 13:16
• intToStr has linear complexity. – Yuval Filmus Jun 12 '19 at 13:20
• WHAT!? i = i // 10 boils down to the number of times we can use integer division to divide i by 10 before getting a result of 0. So the complexity must be O(log(i))! Is that explanation incorrect? – R Doe. Jun 12 '19 at 13:24

To answer your question literally, yes, the code does just return a string of length $$n$$ where $$n$$ is the length of the integer that we pass. And this is the right way to think about it.

Your source, though, is using $$n$$ to denote the value of the integer, not its length. This is an unusual thing to do and it is, in my opinion, a very bad idea when teaching the basics of algorithm analysis. This is a point that students find fundamentally confusing, and your book seems to be contributing to that confusion, instead of reducing it.