Precise runtime of the algorithm to find number of digits in an integer

Consider an integer ( of arbitrary length ). To find the number of digits it has, here is a known simple algorithm

count = 1;
while ( (value = value/10) )    count++;

Now, what is the time cost of this algorithm? If we assume that k is the number of bits ( not digits) required to represent the number, then it is O(k). But this algorithm doesn't have a clean linear behavior. That is, if I double the the number of bits in the integer, the number of iterations of while loop doesn't necessarily double every time. An increase of 3-4 bits in the input increases the iteration count by 1.

I know that the number of digits in a number N is floor(log10(N)) + 1 but then we wouldn't be expressing the runtime in terms of number of bits, which is what I need.

In such cases how to calculate the runtime precisely?

• Why do you 'need' to express the complexity in terms of the number of bits? Who forced you to? – Yuval Filmus Jan 8 '15 at 7:18
• See here. – Raphael Jan 8 '15 at 7:57
• @YuvalFilmus I don't really understand the point of your comment. Sure, you're not forced to measure the complexity in terms of any particular parameter, bit-length of the input is very much the standard measure. Sometimes, there are other natural measures (e.g., the number of vertices in a graph) but I don't see any other natural option here. What would you propose as an alternative? – David Richerby Jan 8 '15 at 9:58
• @DavidRicherby I think Yuval was making the point that he 'wants' to express it in terms of the number of bits. 'needs' suggests somebody else (an instructor?) requires him to. – Tom van der Zanden Jan 8 '15 at 10:43
• @TomvanderZanden If that's the case, I think it's needless and unhelpful pedantry. The question was asked to increase understanding: comments that cause confusion don't bring us any closer to that goal. – David Richerby Jan 8 '15 at 10:45

1. $\log_{10} n = \log_{10} 2 \log_2 n$, and $\log_2 n$ is (almost) the length of $n$ in bits.
2. We don't care about the exact complexity. The point of big O notation is to hide multiplicative constants. A function is $O(\log_2 n)$ iff it is $O(\log_{10} n)$. Moreover, the exact time complexity depends on the exact computation model used (i.e. compiler, CPU, operating system and environment – presumably this code snippet runs on actual hardware and its execution time is measured in seconds), which you haven't specified anyway. Again, the point of big O notation is that these details don't matter since they only affect the complexity by a multiplicative constant.