1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi. I just edited my post to add the complete paragraph, do you still think that it is incorrect? $\endgroup$ – R Doe. Jun 12 at 13:00
  • $\begingroup$ It is correct, just highly misleading. For a similar example, see cs.stackexchange.com/questions/88398/…. $\endgroup$ – Yuval Filmus Jun 12 at 13:02
  • $\begingroup$ 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? $\endgroup$ – R Doe. Jun 12 at 13:16
  • $\begingroup$ intToStr has linear complexity. $\endgroup$ – Yuval Filmus Jun 12 at 13:20
  • $\begingroup$ 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? $\endgroup$ – R Doe. Jun 12 at 13:24
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.