2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why do you 'need' to express the complexity in terms of the number of bits? Who forced you to? $\endgroup$ – Yuval Filmus Jan 8 '15 at 7:18
  • $\begingroup$ See here. $\endgroup$ – Raphael Jan 8 '15 at 7:57
  • 1
    $\begingroup$ @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? $\endgroup$ – David Richerby Jan 8 '15 at 9:58
  • $\begingroup$ @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. $\endgroup$ – Tom van der Zanden Jan 8 '15 at 10:43
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Jan 8 '15 at 10:45
2
$\begingroup$

There are two answers here:

  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.

Another point which you should consider is that in practice, either value has a fixed length, or it is variable length (bignum). If it has fixed length (say it's a 32 bit integer), then the correct parameter here is not the length (which is constant) but the value itself. If it has variable length, then the division instruction cannot be reasonably assumed to take constant time.

$\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.