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