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 $$ \lfloor {\log }_b<!--\; \; -->\left(n\right)\rfloor +1$$, which we proved here. Therefore we can reduce the above algorithm to a $$ \mathrm{\Theta <!--\; \Theta \; -->}\left(1\right)$$ runtime solution as follows

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.