What's kind of funny about the above code is that by assuming it is correct, then the number of iterations is equal to how many digits are in the number in the given base, which turns out to be , which we proved here. Therefore we can reduce the above algorithm to a
Now the runtime of this function is equivalent to two calls of the function log
from math.h
. Read the following discussion to understand the runtime of these functions.